Dark Mode

13,822 views

4 votes

17 votes

Best answer

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.

0

9 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

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**

6 votes

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

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

No.

The time complexity of the following function is $O \left (3^n \right )$ and $\Omega \left ( 3^{n/3} \right )$

def A(n): if n <= 3: return n return A(n-1) + A(n-2) - A(n-3)

This function is a very inefficient function which calculates the value of the time complexity described by the recurrence in the question!

The recurrence for the time complexity of the function $A$ is:

$$T_A(n) = T_A(n-1) + T_A(n-2) \;{\boldsymbol{\Large\color{red}+}}\; T_A(n-3)\; \color{red}{+ O(1)}\\$$

Note: The question already gives us the recurrence. We just have to find the solution.

The recurrence in the question solves to $T(n) = n$ as answered by Amar.

What you are thinking is about an algorithm that computes the value described by the recurrence.

An those two things are very different! :)

3