Question

How to calculate time complexity of binary search tree?

Answer 1

For Binary Search, T(N) = T(N/2) + O(1) // the recurrence relation
Apply Masters Theorem for computing Run time complexity of recurrence relations : T(N) = aT(N/b) + f(N)
Here, a = 1, b = 2 => log (a base b) = 1
also, here f(N) = n^c log^k(n) //k = 0 & c = log (a base b)
So, T(N) = O(N^c log^(k+1)N) = O(log(N))