Search code examples
recursioncomplexity-theory

Complexity analysis of a method

Need to analyze the complexity of recursive function. The function is below.

int hello(int n){
   if(n==0)
       return 0;
   for(int i=0;i<n;i++){
      for(int j=0;j<n * n;j++){
         System.out.println("HELLO");
      }
   }
   return hello(n-1);
}

The step that I am confused is hello(n-1). I don't know how to evaluate a complexity like that code. If you tell the solution of that question step by step, I would be really appreciate. Thanks in advance.

Solution

  • Let the running time of a recursive function is denoted by T(n) where n is the size of the input. In recurrence relation, the running time of a recursive function of input size n is expressed in terms of the running time of the lower value of n. In your case

    T(n) = T(n-1) + n^3 (nested for loops run for O(n^3))

    = T(n-2) + (n-1)^3 + n^3

    = T(n-3) + (n-2)^3 + (n-1)^3 + n^3

    ..... ...... ........

    = T(0) + 1^3 + 2^3 + 3^3 + ....... + (n-2)^3 + (n-1)^3 + n^3

    = 1^3 + 2^3 + 3^3 + ....... + (n-2)^3 + (n-1)^3 + n^3

    = enter image description here

    = O(n^4)

    We can tell its O(n^4) because once we solve it we will ignore all constants and variable with lower exponents in the equation and n^4 would have been the highest power of n.

    Just in case if you heard of master theorem for solving recurrence relation. And wondering how to use that for finding time complexity for this case. You can't because it not in form of T(n) = a*T(n/b) + f(n).

    It may work if you are able to somehow convert it in that form. Not the best option because we already have well known identity to use in this case. Master Theorem is a tool not a liability, use it where you can, otherwise use the best fit method.