Awesome q2a theme
0 votes
31 views
Solve the Given Recurrence using the Substitution method (in book it was Recursion Tree method)

T(n) = 3T(n/2) + n
in Algorithms by (22 points) | 31 views

1 Answer

+3 votes
Best answer

$T(n)=3T\left ( \dfrac{n}{2} \right )+n$

                $\downarrow$

$3\left [3.T\left ( \dfrac{n}{2^2} \right )+\dfrac{n}{2} \right ]+n=3^2T\left ( \dfrac{n}{2^2} \right )+\left ( \dfrac{3}{2} \right )n+n$

                                                         $\downarrow$

$3^2\left [3.T\left ( \dfrac{n}{2^3} \right )+\dfrac{n}{2^2} \right ]+\left ( \dfrac{3}{2} \right )n+n=3^3T\left ( \dfrac{n}{2^3} \right )+\left ( \dfrac{3}{2} \right )^2n+\left ( \dfrac{3}{2} \right )n+n$

.

.

$3^kT\left ( \dfrac{n}{2^k} \right )+\left ( \dfrac{3}{2} \right )^{k-1}n+\left ( \dfrac{3}{2} \right )^{k-2}n\ +.  .   . .+n$

$Now:$

$\dfrac{n}{2^k}=1$

$k=log_{2}n$

 

$3^{log_2{n}}.T(1)+n\left [ \left ( \dfrac{3}{2} \right )^0+\left ( \dfrac{3}{2} \right )^1+\left ( \dfrac{3}{2} \right )^2+. . . . . .\left ( \dfrac{3}{2} \right )^{k-1} \right ]$

$n^{log_{2}3}+n\left [ \dfrac{\left ( \dfrac{3}{2} \right )^k-1}{\dfrac{3}{2}-1} \right ]$

$n^{log_{2}3}+n\left [ \dfrac{\left ( \dfrac{3}{2} \right )^{log_{2}n}-1}{\dfrac{3}{2}-1} \right ]$

$n^{log_{2}3}+2n\left [ \left ( \dfrac{3}{2} \right )^{log_{2}n}-1 \right ]$

$n^{log_{2}3}+2n\left [ \left ( n \right )^{log_{2}(3/2)}-1 \right ]$

$n^{log_{2}3}+2n\left [ \left ( n \right )^{log_{2}3-log_{2}2}-1 \right ]$

$n^{log_{2}3}+2\left [ \left ( n \right )^{log_{2}3-1+1}-n \right ]$


$Ans: 3n^{log_{2}3}-2n$

by (415 points)
selected by
0
small mistake at the end.
0

@ankitgupta.1729

What is that sir? Correct it if possible.

0
bhai, answer should be $3n^{\log_2 3 } - 2n.$ right ?
0
Yes, you are right. I just wrote the TC instead of complete answer.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jul 2020
  1. Shaik Masthan

    39 Points

  2. hiteshpujari

    9 Points

  3. Meghana518

    6 Points

  4. bittujash

    6 Points

  5. Pawan_k

    6 Points

  6. srestha

    5 Points

  7. RavGopal

    4 Points

  8. Anirban Chand

    4 Points

  9. Mk Utkarsh

    4 Points

  10. abcd9982

    3 Points

7,536 questions
1,781 answers
10,866 comments
90,472 users