Register

Time Complexity Equation

513 views
1 votes
1 votes

solve the above question and also calculate the solution for time Complexity Equation. 

User Avatar

1 Answer

1 votes
1 votes
T(n)= T(n-1)+T(n-2)+c

       =O(2^n)

This program is similar to Fibonacci series.The difference is that we need to multiply 1st recursive function by 2 n second recursive function by 3. Here multiply will take constant time.Only recursive functions will contribute to time complexity.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
gateoverflow_ asked Aug 31, 2017
321 views
Time Complexity Equation
how to solve it further?
how to solve it further?
User Avatar
3 votes
3 votes
1 answer
2
sumit_kumar asked Jun 24, 2017
740 views
Recursive equation time complexity
How to apply back substiution method on following recursive equation to find time complexity: T(n)= 2 T(n/2) + (n/log n) , where "n" is input.
How to apply back substiution method on following recursive equation to find time complexity:T(n)= 2 T(n/2) + (n/log n) , where "n" is input.
User Avatar
2 votes
2 votes
1 answer
3
sh!va asked Jul 12, 2016
555 views
Find the complexity of recurrence equation:
A scientist developed a new algorithm for computation and he observed that ot follows the recurrence equation as $T(n) = \begin{cases} 2T(n-1) -1 & \quad if\: n>0 \\ 1 & \quad otherwise \end{cases}$ What is the complexity of new algorithm? $2^n$ $2^{n+1}$ $2^{n-1}$ None of these
A scientist developed a new algorithm for computation and he observed that ot follows the recurrence equation as$T(n) = \begin{cases} 2T(n-1) -1 & \quad if\: n>0 \\ 1 & ...
User Avatar
0 votes
0 votes
0 answers
4
usdid asked Apr 16, 2022
276 views
a) what is the iterative equation showing the running time of the algorithm whose pseudocode is given below? b) What is this repeated equation in asymptotic notation using the Master's theorem. c) What is the same repeated equation in asymptotic notation using the recursion tree method.
a) what is the iterative equation showing the running time of the algorithm whose pseudocode is given below? b) What is this repeated equation in asymptotic notation usin...
User Avatar
Link Copied!