Balanced Search Tree Query, Asymtotic Analysis..
- by AGeek
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.
