retagged by
17,942 views
4 votes
4 votes

retagged by

5 Answers

Best answer
18 votes
18 votes

n should be the correct answer.

T(n) = T(n - 1) + T(n - 2) - T(n - 3)

T(n - 1) = T(n - 2) + T(n - 3) - T(n - 4)

T(n - 2) = T (n - 3) + T(n - 4) - T(n - 5)

T(n - 3) = T (n - 4) + T(n - 5) - T(n - 6)

T(n - 4) = T (n - 5) + T(n - 6) - T(n - 7)

.....................................................

.....................................................

T(6) = T(5) + T(4) - T(3)

T(5) = T(4) + T(3) - T(2)

T(4) = T(3) + T(2) - T(1)

On Adding all the above recurrences, all the red terms of a recurrence will be cancelled out with the red terms of consecutive recurrences, similarly all the blue terms of a recurrence will be cancelled out with the blue terms of consecutive recurrences.

Thus we get

T(n) = T(n - 2) + T(3) - T(1),

but since T(3) =3 & T(1) = 1

so our final recurrence will be T(n) = T(n - 2) + 2

Solution of T(n) = T(n - 2) + 2 will be n.

10 votes
10 votes

$$T(n) = \begin{cases} T(n-1) + T(n-2) - T(n-3) & \mbox{ if } n > 3\\n &  \mbox{ if } n \leq 3\end{cases}$$

From the definition, we can see that:

$T(1) = 1$
$T(2) = 2$
$T(3) = 3$
$T(4) = T(3) + T(2) - T(1) = 3 + 2 - 1 = 4$
$T(5) = T(4) + T(3) - T(2) = 4 + 3 - 2 = 5$
$T(6) = T(5) + T(4) - T(3) = 5 + 4 - 3 = 6$

We can observe the pattern. It looks like $T(n) = n$, but we need to prove it.


Proof by strong induction:

Hypothesis: $T(n) = n$

Base Case: $T(1)$ to $T(6)$ have been shown above.


Assume, for the sake of induction $T(x), \forall x \in [1, n-1]$

Then,

$$\begin{align}T(n) &= T(n - 1) + T(n - 2) - T(n - 3)\\&= (n - 1) + (n - 2) - (n - 3)\\&= n\end{align}$$

QED


So, the answer is option A) n

7 votes
7 votes

It's a homogeneous recurrence relation, and can be solved easily:

$$\begin{align*}
T(n) &= T(n-1) + T(n-2) - T(n-3) \\
a_{n} &= a_{n-1} + a_{n-2} - a_{n-3} \qquad \text{; rewriting recurrence relation}
\end{align*}$$

The characteristic equation will be of the form:

$$\begin{align*}
r^3 &= r^2 + r -1\\
(r+1) (r-1)^3 &= 0
\end{align*}$$

You can now solve it on your own and get $T(n) = \mathcal{O}(n)$

answer = option A

edited by
6 votes
6 votes

ans will be O(3n).. quetion asking about time complexity not value..

evry time 3 call ..and maximum we have n level.. because T(n-1) is given.

Answer:

Related questions

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