1Provide the solution of the average time complexity for the

1.Provide the solution of the average time complexity for the binary search tree.

Reference the binary search tree handout as a reference. Notes: You should assume the binary tree is complete and balanced, and furthermore, assume that the solution exists at one and only one node in the binary tree.

Solution

1)Average time complecity of BST is O(log n) and in worst case O(n).

2) i)T(n)=T(n/2)+1 here b=2 and f(n)=c0=1 and a0=1 in master formula

ii)T(n/2)= T(n/4)+1+1 substituting n/2 in i

Put the value of The(n/2) in above so T(n)=T(n/4)+1+1 . . . . T(n/2^k)+1+1+1.....+1

T(n/2)=T(2^k/2^k)+1+1....+1 up to k

T(n/2)=T(1)+k as we taken 2^k=n

k=log n

So Time complexity is O(log n)