6
$\begingroup$
T(2) = 1 
T(1) = 0

Ans is (3/2)* n - 2

My solution is :

T(n) = 2 T(n/2) + 2
T(n) = 4 T(n/4) + 4
T(n) = 8 T(n/8) + 6
T(n)=(2^k)T(n/2^k) + 2k  
where k = log(n) ..... in base 2
as n/(2^k) = 1 for T(1)

I don't how to solve this type of question to get in terms of n only. Can anyone help me out?

$\endgroup$
4
  • 5
    $\begingroup$ The conditions don't make sense. We have $$T(2)=2T(1)+2=2\neq1.$$ $\endgroup$
    – TheSimpliFire
    Jun 23, 2018 at 14:56
  • 1
    $\begingroup$ @TheSimpliFire: The real is question cdn.geeksforgeeks.org/maximum-and-minimum-in-an-array So the condition is that. $\endgroup$
    – Pygirl
    Jun 23, 2018 at 14:58
  • $\begingroup$ If n is a power of 2, then we can write T(n) as: T(n) = 2T(n/2) + 2 After solving above recursion, we get T(n) = 3n/2 -2 $\endgroup$
    – Pygirl
    Jun 23, 2018 at 14:59
  • $\begingroup$ I am struck at this part. $\endgroup$
    – Pygirl
    Jun 23, 2018 at 14:59

3 Answers 3

8
$\begingroup$

I am a bit confused because as pointed out in the comments, the intial conditions don't exactly make sense. However, just taking T(2) = 1, we can obtain our result:

Since, $T(n) = 2*T(n/2) + 2 => T(n) = 2*(2*T(n/4) + 2) + 2 => T(n) = 2^2*T(n/2^2) + 2^2 + 2$

Proceeding further we get $T(n) = 2^2 * (2*T(n/2^3)+2) + 2^2 + 2 => T(n) = 2^3*T(n/2^3) + 2^3 + 2^2 + 2$

As you can see, the relation we get now is $T(n) = 2^k T(n/2^k) + 2 + 2^2 +...+2^k$

Now because I want to use the initial condition, let $n = 2^{k+1}$ Therefore, $T(n) = \frac{2^{k+1}}{2}T(\frac{2^{k+1}}{2^k}) + 2 + 2^2 +...+ 2^k$

Therefore, $T(n) = \frac{n}{2}T(2) + 2 + 2^2 +...+ 2^k$

Since, $2 + 2^2 +...+ 2^k$ is a geometric progression, using the formula for a geometric progression sum, we get $2 + 2^2 +..+2^k = \frac{2(1-2^k)}{1-2} = 2(2^k-1) = 2(\frac{n}{2} - 1)$

Using this result and the fact that T(2) = 1, we get $T(n) = \frac{n}{2}(1) + 2(\frac{n}{2}-1) = \frac{n}{2} + n - 2 = \frac{3n}{2} - 2$.

$\endgroup$
2
  • 1
    $\begingroup$ Do let me know if there are any steps I need to clarify further! $\endgroup$
    – S.walia
    Jun 23, 2018 at 17:22
  • $\begingroup$ It explains everything :) .Thanx Mr walia for explaining it . $\endgroup$
    – Pygirl
    Jun 23, 2018 at 18:01
2
$\begingroup$

Hint.

Make $t_n = \log(a^n)+b$

so we have

$$ n\log a + b = 2\left(\frac n2\log a+ b\right)+2\to b = -2 $$

now assuming $t_2 = 2\log a - 2 = 1$ we have

$$ t_n = \frac {3n}{2} - 2 $$

$\endgroup$
5
  • $\begingroup$ I didn't get this one. $\endgroup$
    – Pygirl
    Jun 23, 2018 at 17:57
  • $\begingroup$ How did you reached to tn = (3/) * n - 2 ? $\endgroup$
    – Pygirl
    Jun 23, 2018 at 17:59
  • $\begingroup$ okay a = 2^(3/2) but how did u come up with log a^n - 2 ?? $\endgroup$
    – Pygirl
    Jun 23, 2018 at 18:05
  • 1
    $\begingroup$ The general solution for this type of difference equation is $t_n = \log(a^n)+b$ Substituting the general solution we can define the $b$ value and with the initial condition we fix the $a$ value. Is much like the procedure with the differential equation. $\endgroup$
    – Cesareo
    Jun 23, 2018 at 19:14
  • $\begingroup$ Thanx for the info :). $\endgroup$
    – Pygirl
    Jun 24, 2018 at 3:35
1
$\begingroup$

T(n) = 2T(n/2) + 2 and T(n/2) = 2T(n/4) + 2 so if you put those together you get T(n) = 4T(n/4) + 6. Similarly T(n) = 8T(n/8) + 14.

You should stop the recursion one step sooner when argument to T is 2, since as noted in comment the recursion formula doesn’t hold from T(2) to T(1). To finish it, note that 2^(k-1) = n/2.

So, if n = 2^k after iterating k-1 times you get T(n) = 2^(k-1) T(n/2^(k-1)) + 2^k - 2 = n/2 T(2) + n - 2

$\endgroup$
3
  • $\begingroup$ I know that .I was having problem in generalizing it in terms of n. $\endgroup$
    – Pygirl
    Jun 23, 2018 at 17:56
  • $\begingroup$ Edited to add the result after k-1 steps in terms of n. Hope that helps. $\endgroup$
    – dioid
    Jun 23, 2018 at 18:14
  • $\begingroup$ Thanx .It helps. $\endgroup$
    – Pygirl
    Jun 24, 2018 at 3:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .