To get time complexity of recursive functions/calls, we first also show time complexity as recursive manner.
** Time complexity in recursive form
We first have to create a way to describe time complexity of recursive functions in form of an equation as,
\[ T(n) = ( \text{Recursive calls by the function} ) + ( \text{Time taken per call, i.e, the time taken except for recursive calls in the function} ) \]
+ Example, suppose we have a recursive function
#+BEGIN_SRC c
int fact(int n){
if(n == 0 || n == 1)
return 1;
else
return n * fact(n-1);
}
#+END_SRC
in this example, the recursive call is fact(n-1), therefore the time complexity of recursive call is T(n-1) and the time complexity of function except for recursive call is constant (let's assume *c*). So the time complexity is
\[ T(n) = T(n-1) + c \]
\[ T(1) = T(0) = C\ \text{where C is constant time} \]
+ Another example,
#+BEGIN_SRC c
int func(int n){
if(n == 0 || n == 1)
return 1;
else
return func(n - 1) * func(n - 2);
}
#+END_SRC
Here, the recursive calls are func(n-1) and func(n-2), therefore time complexities of recursive calls is T(n-1) and T(n-2). The time complexity of function except the recursive calls is constant (let's assume *c*), so the time complexity is
\[ T(n) = T(n-1) + T(n-2) + c \]
\[ T(1) = T(0) = C\ \text{where C is constant time} \]
+ Another example,
#+BEGIN_SRC c
int func(int n){
int r = 0;
for(int i = 0; i < n; i++)
r += i;
if(n == 0 || n == 1)
return r;
else
return r * func(n - 1) * func(n - 2);
}
#+END_SRC
Here, the recursive calls are func(n-1) and func(n-2), therefore time complexities of recursive calls is T(n-1) and T(n-2). The time complexity of function except the recursive calls is *\theta (n)* because of the for loop, so the time complexity is
\[ T(n) = T(n-1) + T(n-2) + n \]
\[ T(1) = T(0) = C\ \text{where C is constant time} \]
* Solving Recursive time complexities
** Iterative method
+ Take for example,
\[ T(1) = T(0) = C\ \text{where C is constant time} \]
\[ T(n) = T(n-1) + c \]
We can expand T(n-1).
\[ T(n) = [ T(n - 2) + c ] + c \]
\[ T(n) = T(n-2) + 2.c \]
Then we can expand T(n-2)
\[ T(n) = [ T(n - 3) + c ] + 2.c \]
\[ T(n) = T(n - 3) + 3.c \]
So, if we expand it k times, we will get
\[ T(n) = T(n - k) + k.c \]
Since we know this recursion *ends at T(1)*, let's put $n-k=1$.