13,822 views

sir can u solve this?
you can see the answer by Umang below. Just do the changes in it and you will get it.
what should be the relation between T(1),T(2),T(3) so that the algorithm time complexity  becomes constant?

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.

T(n) = n if n ≤ 3 means T(1) = 1 T(2) = 2  T(3) = 3

after subtracting you will be left T(6)=T(4)-2  . right!

Yes umang, I made a little mistake here. T(n) = T(n - 2) + 2. & The answer should be n.
Thanks for pointing that out. Edited it.
we are talking aboue time complexity of the program but not the returned value of the program.
we can not cancel one time complexity with other time complexity.

Can you prove that this program will be executed only n times. and how do you know the complexity of T(n-2) will be (n-2) or O(n)?

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

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)$

i think ur going for dynamic programing..
Does the length of the longest path in the recursion tree is equal to Time complexity??
updated.

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! :)

ok got it. (y)

1
1,883 views