Binary Search Tree's Sorting

This sounds like homework, which means you can ask for help but not for answers

Quote:

Original post by Extrarius This sounds like homework, which means you can ask for help but not for answers

i did it myself once.. but not sure if i am correct
i found it to be (nlgn) and (n^2) for best and worst.

but to my understanding..
constructing a binary tree = O(nlgn)
in-order-walk = O(n)

shouldnt it be O(n(1+lgn))

When two terms are added, if you take the limit going to infinity, one of them will be much larger than the other. That is the whole idea of asymptotic notation, and when comparing "n" to "n*log(n)", the latter will be far larger with huge numbers and is thus the only one considered.

Quote:

Original post by Extrarius When two terms are added, if you take the limit going to infinity, one of them will be much larger than the other. That is the whole idea of asymptotic notation, and when comparing "n" to "n*log(n)", the latter will be far larger with huge numbers and is thus the only one considered.

o.. really...
so. just take o(nlgn) as the best case?

if so.. for the worst case:
since.. worst time for contructing a binary tree would be n^2
and so it would be n + n^2 => O(n^2)
rite?

Yes[smile]