[EMAIL PROTECTED] wrote:
> Hi Gene,
> can u tell me what is the time complexity of your code?
>
> VishnuPriya
The code is copied below. (Note I fixed a typo in the original; the
variable "ir" should have been delared an integer not a char.)
Each iteration of the loop has constant run time. It either adds a
character to the output buffer (the line that does this is r[ir--] =
s[is--]; ) or else it prints the buffer. So it's easy to see the run
time is O(L) where L is the length of the output. It's hard to imagine
where a faster algorithm would be useful. The stack iss needs as many
slots as there are characters in each output subsequence.
void print_all_subsequences(char *s, int is, char *r, int ir)
{
int iss[1000], *isp = iss, irs = ir;
for (;;) {
if (ir < 0) {
printf("\n%s", r);
if (isp == iss)
break;
is = --*isp;
ir = ++irs;
}
else {
r[ir--] = s[is--];
if (is > ir) {
--irs;
*isp++ = is;
}
}
}
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
