2
$\begingroup$

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.

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

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. $$

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

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})$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.