algorithm

Question

some random numbers are given and asked to construct a balanced BST..what will be the time complexity?

numbers in sorted order are given and asked to construct a balanced BST...what will be the time complexity??

Answer 1

I think,
a. O(n^2)
b. O(nlogn)

Comments

O(n^2) should be for the second case right??

ascending or descending then it forms a skew tree

therefore O(n^2)

and a small change in the question...its balanced BST not BST

---

I can choose middle key as root of bst and then can recursively call a function on left and right sub parts. so it will be a balanced Binary Search Tree at the end,

---

am concerned with the time complexity

for this procedure its O(n log n)

i cannot understand how