Determining complexity for recursive functions (Big O notation)

Question

I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve these harder cases. These were just a few of the example problems that I could not figure out. Any help would be much appreciated and would greatly help in my studies, thank you!

int recursiveFun1(int n) {     if (n <= 0)         return 1;     else         return 1 + recursiveFun1(n-1); }  int recursiveFun2(int n) {     if (n <= 0)         return 1;     else         return 1 + recursiveFun2(n-5); }  int recursiveFun3(int n) {     if (n <= 0)         return 1;     else         return 1 + recursiveFun3(n/5); }  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);     } }  int recursiveFun5(int n) {     for (i = 0; i < n; i += 2) {         // do something     }      if (n <= 0)         return 1;     else         return 1 + recursiveFun5(n-5); } 

Answer 1

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 2

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)