Register

Time Complexity Equation

875 views
1 1 vote

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

1 Answer

1 1 vote
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.
Voting & Accepting an answer helps improve the community
← Previous · can any one explain ...Next → · Gate CE 2005 linear ...
← Previous in category · C programming on que...Next in category → · functions in c
Position:
Show:

Related questions

0 0 votes
1 1 answer
740
740 views
gateoverflow_ asked Aug 31, 2017
740 views
Time Complexity Equation
how to solve it further?
3 3 votes
1 answers 1 answer
1.1k
1.1k views
sumit_kumar asked Jun 24, 2017
1,098 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.
2 2 votes
1 answers 1 answer
997
997 views
sh!va asked Jul 12, 2016
997 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 & ...
0 0 votes
0 0 answers
528
528 views
usdid asked Apr 16, 2022
528 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...