The time complexity, in Big O notation, for each function:
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
This function is being called recursively n times before reaching the base case so its O(n), often called linear.
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
This function is called n-5 for each time, so we deduct five from n before calling the function, but n-5 is also O(n).
(Actually called order of n/5 times. And, O(n/5) = O(n) ).
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
This function is log(n) base 5, for every time we divide by 5
before calling the function so its O(log(n))(base 5), often called logarithmic and most often Big O notation and complexity analysis uses base 2.
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
Here, it's O(2^n), or exponential, since each function call calls itself twice unless it has been recursed n times.
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
And here the for loop takes n/2 since we're increasing by 2, and the recursion takes n/5 and since the for loop is called recursively, therefore, the time complexity is in
(n/5) * (n/2) = n^2/10,
due to Asymptotic behavior and worst-case scenario considerations or the upper bound that big O is striving for, we are only interested in the largest term so O(n^2).
Good luck on your midterms ;)
Answer from coder on Stack OverflowTime complexity of recursive Fibonacci program
recursion - Determining complexity for recursive functions (Big O notation) - Stack Overflow
How to calculate the time complexities of recursive functions ??
Why is recursion so praised despite it typically using more memory and not being any faster than iteration?
The time complexity, in Big O notation, for each function:
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
This function is being called recursively n times before reaching the base case so its O(n), often called linear.
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
This function is called n-5 for each time, so we deduct five from n before calling the function, but n-5 is also O(n).
(Actually called order of n/5 times. And, O(n/5) = O(n) ).
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
This function is log(n) base 5, for every time we divide by 5
before calling the function so its O(log(n))(base 5), often called logarithmic and most often Big O notation and complexity analysis uses base 2.
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
Here, it's O(2^n), or exponential, since each function call calls itself twice unless it has been recursed n times.
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
And here the for loop takes n/2 since we're increasing by 2, and the recursion takes n/5 and since the for loop is called recursively, therefore, the time complexity is in
(n/5) * (n/2) = n^2/10,
due to Asymptotic behavior and worst-case scenario considerations or the upper bound that big O is striving for, we are only interested in the largest term so O(n^2).
Good luck on your midterms ;)
For the case where n <= 0, T(n) = O(1). Therefore, the time complexity will depend on when n >= 0.
We will consider the case n >= 0 in the part below.
1.
T(n) = a + T(n - 1)
where a is some constant.
By induction:
T(n) = n * a + T(0) = n * a + b = O(n)
where a, b are some constant.
2.
T(n) = a + T(n - 5)
where a is some constant
By induction:
T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)
where a, b are some constant and k <= 0
3.
T(n) = a + T(n / 5)
where a is some constant
By induction:
T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)
where a, b are some constant
4.
T(n) = a + 2 * T(n - 1)
where a is some constant
By induction:
T(n) = a + 2a + 4a + ... + 2^(n-1) * a + T(0) * 2^n
= a * 2^n - a + b * 2^n
= (a + b) * 2^n - a
= O(2 ^ n)
where a, b are some constant.
5.
T(n) = n / 2 + T(n - 5)
where n is some constant
Rewrite n = 5q + r where q and r are integer and r = 0, 1, 2, 3, 4
T(5q + r) = (5q + r) / 2 + T(5 * (q - 1) + r)
We have q = (n - r) / 5, and since r < 5, we can consider it a constant, so q = O(n)
By induction:
T(n) = T(5q + r)
= (5q + r) / 2 + (5 * (q - 1) + r) / 2 + ... + r / 2 + T(r)
= 5 / 2 * (q + (q - 1) + ... + 1) + 1 / 2 * (q + 1) * r + T(r)
= 5 / 4 * (q + 1) * q + 1 / 2 * (q + 1) * r + T(r)
= 5 / 4 * q^2 + 5 / 4 * q + 1 / 2 * q * r + 1 / 2 * r + T(r)
Since r < 4, we can find some constant b so that b >= T(r)
T(n) = T(5q + r)
= 5 / 2 * q^2 + (5 / 4 + 1 / 2 * r) * q + 1 / 2 * r + b
= 5 / 2 * O(n ^ 2) + (5 / 4 + 1 / 2 * r) * O(n) + 1 / 2 * r + b
= O(n ^ 2)
I mean, most of the time, i always write top down recursive code for dynamic programming but most of the times im unable to calculate the time complexities.
Is there any way in which i can do this ??