World's most popular travel blog for travel bloggers.

Time complexity of a Divide and Conquer

, , No Comments
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?

Asked By : iankit3
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$.)

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback