Master Theorem gives different results from Iteration solving Recurrence Relation

108 Views Asked by At

Trying to find a solution iteratively to this recurrence relation: $T(n) = 2T(n/2) + \log n $

$T(n) = 2^k T(n/2^k) + \sum_{i=0}^{k-1} 2^i \log \dfrac{n}{2^i} = n*1 + \sum_{i=0}^{k-1}2^i\log n - 2^i \log2^i \leq n + \log n \sum_{i=0}^{k-1} 2^i = n + \log n * (n-1) = O(n\log n)$

I obtain $O(n\log n)$ which is different from the result obtained using the Master Theorem: $O(n)$
Is it possible or I'm just doing it the wrong way?

1

There are 1 best solutions below

1
On BEST ANSWER

Look at $T(2^k)$, you have $T(2^k)=2T(2^{k-1})+k=4T(2^{k-2})+k+2(k-1)$, following this general pattern you see $T(2^k)=2^kT(1)+\sum_{j=1}^k 2^j(k-j)$ (or something equal to that modulo a fencepost error that doesn't matter for the asymptotics). You can change variables to $i=k-j$ so that $j=k-i$, so you have $2^k \sum_{i=0}^{k-1} i 2^{-i}$ whose dominant term is proportional to $2^k$.

Your mistake appears to be caused by too bluntly estimating the sum, since it is true that $\sum_{j=1}^k 2^j k$ scales like $O(n\log(n))$. But in some sense "most" of this sum is cancelled out by the $-j$ part.