Question

Find the runtime of this function, where n is an integer.

int function(int n) {
  int a = 0;
  for (int i = n; i > 0; i--) {
    for (int j = 0; j < i; j++) {
      a = a + i + j;
    }
  }
  return a;
}

Find the runtime of this function, where m and n are two integers.

int f(int m, int n) {
  if (m==1 || n==1) {
    return 1;
  }
  return f(m, n-1) + f(m-1, n);
}

Please explain to me each of the steps and how you receive the answer.

Thank you

Answer 1

Please find the answer for the above given question.

ANSWER :

For Question 1 :

int function(int n) {
  int a = 0;
  for (int i = n; i > 0; i--) {
    for (int j = 0; j < i; j++) {
      a = a + i + j;
    }
  }
  return a;
}

answer : O(n^2) [Big O of n square]

Explanation :

For an example if we consider the n value as 5 . Outer loop will run for 5 times total , we can say that directly based on the condition and decrement that is happening in the first loop. But the inside loop will run based on the i value that is coming from the outer loop. So we write step by step , we can observe the below thing.

when i value is 5 , j loop also will run for 5 times,

when i value is 4 , j loop also will run for 4 times

when i value is 3 , j loop also will run for 3 times

when i value is 2 , j loop also will run for 2 times

when i value is 1 , j loop also will run for 1 times

So if we calculate the number of runs total 5+4+3+2+1 = n(n+1)/2 = O(n^2)/2 + O(n/2) = O(n^2) + O(n) = O(n^2)

Time complexity = O(n^2)

For Question 2 :

int f(int m, int n) {
  if (m==1 || n==1) {
    return 1;
  }
  return f(m, n-1) + f(m-1, n);
}

answer :   O(m+n) [BIg O of m plus n]

Explanation :

For an example if we consider m value as 6 and n value as 7 , So function will be called initially with m and n values as 6 and 7 respectively. until unless m value or n value is 1 recursive calls will happen. So the first recursive call will happen with m value as same but the n value will be decremented by 1 and other function call is m value is decremented by 1 and n value is same.

So the first function will run for n times and the second function will run for m times.

Number of times call will happen to function f is = m+n

Time complexity = O(m+n)

Thanks..