in Algorithms retagged by
13,822 views
4 votes
4 votes

in Algorithms retagged by
13.8k views

4 Comments

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

5 Answers

17 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.

selected by

4 Comments

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!

0
0
Yes umang, I made a little mistake here. T(n) = T(n - 2) + 2. & The answer should be n.
0
0
Thanks for pointing that out. Edited it.
0
0
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)?
0
0
9 votes
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
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

3 Comments

i think ur going for dynamic programing..
1
1
Does the length of the longest path in the recursion tree is equal to Time complexity??
0
0
updated.
0
0
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.

2 Comments

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
3
ok got it. (y)
1
1
Answer:

Related questions