1,385 views

3 Answers

1 votes
1 votes
I got theta(3^n) using the recursion tree, under the ASSUMPTION that base case is theta(1). Each problem is getting divided into 3 sub problems. Height of the tree = theta(n), number of leaves or nodes at any height h = 3^h. Number of leaves at the lowest level = 3^n. Total number of leaves + internal nodes in the tree = 3^0 + 3^1 + 3^2 + ...+3^n = theta(3^n). Constant time "c" at each leaf or internal node, so total time should be theta(3^n).
0 votes
0 votes

lets T(n) =r^n
so its corresponding recurrence eqn will be     r^n =2r^(n-1)  +  r^(n-2) {not considering c as it will affect the complexity}
                                                                      =r^2=2r+1
                                                                       =r^2-2r-1=0
                     r=1+root(2)  and 1-root(2)
so, T(n) = a[1+root(2)]^n  +  b*(1-root(2))^n

since t(0)=t(1)=1

putting these value in the eqn we will get

       t(0) = a+b=1

      t(1) = a(1+root(2)) +b(1-root(2))=1

solving these 2 eqn gives

  a=1/2 and b=1/2

so , t(n)=((1+root(2))^n  + (1-root(2))^n)/2

            = 0((1+root(2)^n))                 {1+root(2)is the leading tern in the eqn}

            0(2.4n)

Related questions

2 votes
2 votes
1 answer
1
Ashwani Kumar 2 asked Sep 8, 2016
3,414 views
1. T(n) = T(n-a) + T(a) + cn2. T(n) = T(αn) + T( (1-α)n ) + cnwhere α, a and c are constant.
1 votes
1 votes
1 answer
3
sripo asked Nov 14, 2018
1,570 views
T(n)=T(n/2)+2; T(1)=1when n is power of 2 the correct expression for T(n) is:a) 2(logn+1)b) 2lognc)logn+1d)2logn+1