How this complexity calculation

51 Views Asked by At

I'm not familiar with this complexity calculations. Someone could tell me how

T(n) = T(n/2) + θ(1) become T(θ) = θ(log2 n)

log2 means base is 2 for log

This is related to peek finding algorithm for a 1D array with n number of elements.

1

There are 1 best solutions below

0
On

Using Master's Method case 2 is applicable since $n^{\log_b a}=n^{\log_2 1}=1$ which is equal to $\theta(1)$. Thus from Master's method $T(n)=\theta(n^{\log_2 1}\log n) = \theta(\log n)$