ISRO-DEC2017-18

Question

Consider the recurrence equation

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

Then $T(n)$ is (in $big\, O$ order)

• A. $O(n)$
• B. $O(2^n)$
• C. $O(1)$
• D. $O(\log n)$

Comments

T(n) = 2T(n-1), T(0) = 1

solving this linear homogenouss equaition we will get, $T(n)=2^{n}$

so it will be $O(2^{n})$

---

isro says O(1)

---

it should be O(2ⁿ) only, if it T(0) = 0, then it would be O(1)

---

Surely O(2ⁿ)

Answer 1

$T(n)=2T(n-1)$

$T(n)=2[2T(n-2)]=2^{2}T(n-2)$

$T(n)=2^{2}[2T(n-3)]= 2^{3}T(n-3)$

$T(n)=2^{k}T(n-k)$

$n-k=0, \ n=k,\ T(0)=1$

$T(n)=2^{n}$

Hence option B) is correct

Comments

They even didnt change this in the revised key...

---

Maybe because nobody submitted any grievance against it.

---

I think ISRO is correct. Because the time complexity depends on the workdone. so T(n) = 2T(n - 1) + 0 means with no time it can do that. So directlty we can say that T(n) = 2^n for example T(3) = 8 directly i can say.

---

 papujimmy no you are a little wrong that extra amount of work you are mentioning is not done in this recurrence, if it is not done or that work is less as compared to recurrence then that is not considered while calculating complexity.

Answer 2

just do  by substitution nd observation for saving tym

T(0)=1 given

T(1)=2 on putting

T(2)=2*2

T(3)=2*2*2

...............T(n)=2*2*2*2.............n tymes=2^n