World's most popular travel blog for travel bloggers.

# Time complexity of a Divide and Conquer

, ,
Problem Detail:

I have Master theorem for finding complexities but the problem is Master theorem says

For a recurrence of form $T(n) = aT(n/b) + f(n)$ where $a \geq 1$ and $b > 1$, there are following three cases:

• if $f(n) = Θ(n^c)$ where $c < \log_ba$, then $T(n) = Θ(n\log_ba)$;

• if $f(n) = Θ(n^c)$ where $c = \log_ba$, then $T(n) = Θ(nc\log n)$;

• if $f(n) = Θ(n^c)$ where $c > \log_ba$, then $T(n) = Θ(f(n))$.

I have$T(n) = T(n/2) + n^2$.

My solution is that $c = 2$ and $\log_ba = \log_1 2=\infty$. So in which case does it fall and what is the complexity?

###### Answered By : David Richerby

As Rick Decker points out in his comment, your error is that you have $a=1$, $b=2$, so $\log_ba = \log_21=0$. (Not, as you say, $\log_ba=\log_12$.)