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

2 Answers 2

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

$\endgroup$
2
  • $\begingroup$ I don't want to use substitution. $\endgroup$
    – Einzig7
    Jul 29, 2018 at 17:46
  • $\begingroup$ My starting point is the expression you reached (for arbitrary $T(1)$). $\endgroup$ Jul 29, 2018 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})$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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