# Time complexity calculation

I was calculating the time complexity of the following recurrence relation given that T(1) = 1 :

T(n) = 2T(n/2) + Logn

I was calculating the value and this is where I reached:

T(n) = logn + 2log(n/2) + 4log(n/4) + 8log(n/8) + .....+ 1

I have tried solving this by opening log but I'm unable to reach O(n). I don't want any other method like substitution or root tree to be used. I want to use simple maths and reach O(n), please let me know if you have a clue about it.

• What is the time complexity of a recurrence? Perhaps you want an asymptotic estimate for the solution of the recurrence instead? – Yuval Filmus Jul 29 '18 at 17:21
• Are you familiar with the master theorem? – Yuval Filmus Jul 29 '18 at 17:21
• @YuvalFilmus I dont want to use masters theorem, I want to use simple maths. – Einzig7 Jul 29 '18 at 17:45
• Your expression for $T(n)$ is wrong. The last summand should be $n$ rather than $1$. – Yuval Filmus Jul 29 '18 at 17:56

Suppose that $n = 2^k$, and that the logarithm is base 2. Then $$T(2^k) = \log (2^k) + 2 \log(2^{k-1}) + 4 \log(2^{k-2}) + \cdots + 2^{k-1} \log 2 + 2^k T(1) \\ = k + 2(k-1) + 4(k-2) + \cdots + 2^{k-1}(k-(k-1)) + 2^k T(1) \\ = (1+2+4+\cdots + 2^{k-1})k - (2^1 \cdot 1 + 2^2 \cdot 2 + \cdots + 2^{k-1}(k-1)) + 2^kT(1).$$ The first summand is equal to $(2^k-1)k$. The second is equal to $$(2^1 + \cdots + 2^{k-1}) + (2^2 + \cdots + 2^{k-1}) + \cdots + (2^{k-1}) = \\ (2^k-2^1) + (2^k-2^2) + \cdots + (2^k-2^{k-1}) = \\ (k-1)2^k - (2^1 + 2^2 + \cdots + 2^{k-1}) = \\ (k-1)2^k - (2^k-2) = (k-2)2^k + 2.$$ In total, we get $$T(2^k) = (k2^k - k) - (k2^k - 2^{k+1} + 2) + 2^k T(1) = 2^{k+1} - k - 2 + 2^k T(1).$$ In terms of $n$, this is $$T(n) = (2 + T(1))n - \log n - 2.$$

• I don't want to use substitution. – Einzig7 Jul 29 '18 at 17:46
• My starting point is the expression you reached (for arbitrary $T(1)$). – Yuval Filmus Jul 29 '18 at 17:54

Fix the one error in the calculation, and order the terms with the largest first: $T(n) = n + \log 2 n/2 + \log 4 n/4 + \log 8 n/8 ...$

Now replace $\log n$ with the larger $n^{1/2}$ and you get

$T(n) ≤ n + 2^{1/2} n/2 + 2^{1/4} n/4 + 2^{1/8} n/8 ...$

$T(n) ≤ n (1 + 2^{-1/2} + 4^{-1/2} + 8^{-1/2} ...)$

That's a geometric series that converges to $n / (1 - 0.5^{1/2})$