Question

Time complexity to search for an element in a balanced bst with (2n)! Elements?

Answer 1

Worst case time to search an element in  balanced BST with n element =log₂n

Here we have (2n)! element So time complexity will be=log₂ (2n)!

                                                                                     =log₂2n²ⁿ

                                                                                     =2n log₂2n

                                                                                     =2n(log₂2 +log₂n)

                                                                                     =2nlog₂n

                                                                                                                 _{^{= O(nlogn)}}

Comments

How log₂(2n)!=log₂2n²ⁿ

---

for upper bound we can assume,  n! = n^n

---

log(2n!)=log(2n*2n-1*............2*1)

        <=log2n2n

        =O(nlogn)