edited by
537 views
2 votes
2 votes

A scientist developed a new algorithm for computation and he observed that ot follows the recurrence equation as

$T(n) = \begin{cases} 2T(n-1) -1 & \quad  if\: n>0 \\ 1 & \quad otherwise \end{cases}$

What is the complexity of new algorithm?

  1. $2^n$
  2. $2^{n+1}$
  3. $2^{n-1}$
  4. None of these
edited by

1 Answer

Best answer
4 votes
4 votes

By iterative method:

$T(n)=2T(n-1)-1 =4T(n-2)-3 =8T(n-3)-7 ....=2^iT(n-i)-(2^i-1)$

The algorithm converges when T(n)=T(0), i.e when i=n.

when i=n, $T(n)=2^iT(n-i)-(2^i-1)$ become

$T(n)=2^nT(0)-(2^n-1)$

=$2^n-(2^i-1)$

=$2^n-2^i+1$

=1

i.e O(1).

Answer is D none of the above option.

selected by

Related questions

0 votes
0 votes
0 answers
1
pk14697 asked Jul 2, 2018
321 views
To prove that the time complexity of equationT(n) = T(α n) + T((1 – α)n) + βnisΘ(n logn).
1 votes
1 votes
2 answers
2
1 votes
1 votes
0 answers
3
iarnav asked Jan 14, 2018
187 views
what is recurrence relation of harmonic number/series ? and it's time complexity
4 votes
4 votes
0 answers
4
Aakanchha asked Jan 8, 2018
797 views
What is the highest upper bound time complexity for the following recurrence equation: $T(n)=4T\lef...