On Jul 1, 4:04 pm, jalaj jaiswal <[email protected]> wrote: > i was talking about the space complexity.. running time is obvs O(n)
Hello J.J. Why would those 3 lines of executable code you cited say anything about space complexity? They don't allocate memory. You must be quibbling. There's no issue with space either. Whatever space the lookup table takes is O(M) where M is the number of distinct symbols. But if you didn't have the table, you'd need a chain of "if"s or a switch (as the other posted solutions use), which compile to code that's O(M) in size. It's a wash. Finally, if the number of symbols M were large, you could use a O(1) time lookup scheme like a perfect hash to avoid the O(M) factor of runtime for the linear lookup. Cheers. > On Thu, Jul 1, 2010 at 9:14 PM, Gene <[email protected]> wrote: > > On Jun 30, 3:38 am, Debajyoti Sarma <[email protected]> wrote: > > > @Gene > > > your code's last 3 line gives doubt. > > > ....... > > > for (i = j = 0; j < M; j++) > > > while (c[j]--) > > > a[i++] = j; > > > ....... > > > Is it don't make the complexity more than O(n) ?? > > > Not at all. The inner loop body executes n times no matter what the > > value of M is. > > > Guys, this is just a special case of counting sort. Obviously O(n). > > > -- > > 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]<algogeeks%2bunsubscr...@googlegroups > > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD -- 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?hl=en.
