One thing you need to keep in mind about finding the time complexity of a recursive function is recurrence relation.
Below is a C function for finding the fibonacci sequence (same as yours):
int fib(int n)
{
if((n==1) ||(n==2))return 1;
return (fib(n-1)+fib(n-2));
}
Converting the above code into a Recurrence Relation:
T(0) = 0 ......base case
T(n) = 2T(n-1) + 1
Sol'n
T(n) = 2T(n-1) + 1
= 2(2T(n-2) + 1) + 1
= 4(2T(n-3) + 1) + 1 + 2
:
:
= 2^k T(n-k) + ∑ 2^i
= 2^k T(n-k) + 2^(k-1)
= 2^k T(n-k) + (2^k) - 1 using 1-r^n / 1-r
Now,
n-k = 0
n=k
Finally,
T(n) = 2^n T(n-n) + 2^n - 1
= 2^n T(0) + 2^n - 1
= 0 + 2^n - 1
= 2^n - 1
Order:
O(2^n) .....Time Complexity
time complexity --- O(2^n)
space complexity-----O(n)
draw recursive tree and calculate its height or depth that will be space complexity
Reference:
http://cs.stackexchange.com/questions/14733/complexity-of-recursive-fibonacci-algorithm
相关推荐
Calculating Hypervolume is one of the ... In this paper,We have gotten HSO algorithm's time complexity by the path problem of combinatorial mathematics, and described the mapping between the two issues.
Complexity of Algorithms
Algorithm and Complexity
It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing...measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.
The of Boolean Functions
《complexity of algorithms》 written by Peter G´acs (Boston University)and L´aszl´o Lov´asz(Yale University)
Measuring Cyclomatic Complexity Of Python Code
The Computational Complexity of Machine Learning
In view of the higher time complexity of traditional copy-move forgery detection, bad robustness for the image rotation zoom and other follow-up retouching operations, a copy-move forgeries detection ...
For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to ...
Holderian增长下凸优化非精确近点算法的计算复杂性_Computational complexity of Inexact Proximal Point Algorithm for Convex Optimization under Holderian Growth.pdf
能用这一工具来证明在密码学中某些安全性问题。
The time complexity analysis of a class of gene expression programming
这本书是关于算法和复杂性,因此它在解决问题的方法上 计算机和费用(通常是运行时间),使用这些方法。 计算需要时间。有些问题需要很长的时间其他人就可以迅速完成。一些问题 似乎需要很长时间,然后有人发现一个...
Theory of Computational Complexity offers a thorough presentation of the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization, and the ...
Millimeter wave (mmWave) ... In this paper, we transform the hybrid precoding problem and develop a low complexity joint hybrid precoding algorithm. First, the analog precoder and combiner are ob
Theory of Computation covers regular, context-free, and general phrase-structure languages along with their associated automata, computability in the context of Turing machines, partial recursive ...