Balanced Search Tree Query, Asymtotic Analysis..

Question

Hi,

The situation is as follows:-

We have n number and we have print them in sorted order. We have access to balanced dictionary data structure, which supports the operations serach, insert, delete, minimum, maximum each in O(log n) time.

We want to retrieve the numbers in sorted order in O(n log n) time using only the insert and in-order traversal.

The answer to this is:-

Sort()
  initialize(t)
  while(not EOF)
     read(x)
     insert(x,t);
  Traverse(t);

Now the query is if we read the elements in time "n" and then traverse the elements in "log n"(in-order traversal) time,, then the total time for this algorithm (n+logn)time, according to me.. Please explain the follow up of this algorithm for the time calculation.. How it will sort the list in O(nlogn) time??

Thanks.

Answer 1

Each insert is O(log n). You are doing n inserts, so that gives n * O(log n) = O(n log n) asymptotic time complexity. Traversing the tree is O(n), because there are n nodes. That adds up to O(n + n log n) which differs from O(n log n) by a constant, so the final asymptotic complexity is O(n log n)..

and then traverse the elements in "log n

Traversal is O(n), not O(log n). An insertion is O(log n), and you're doing n such insertions.