If my method with time complexity O(n^2) uses another method with time complexity O(n) does its time-CodePudding

The what method has a time complexity of O(n^2) and it uses the method f with time complexity of O(n). I need to calculate the overall time complexity of method what. Do I also take in account the time complexity of method f, so overall the time complexity of method what would be O(n^2 * n = n^3), or does each method take care of its own time complexity, so in this case the method what will stay at time complexity O(n^2)?

private static int f (int[]a, int low, int high)
{
    int res = 0;
    for (int i=low; i<=high; i  )
        res  = a[i];
    return res;
}

public static int what (int []a)
{
    int temp = 0;
    for (int i=0; i<a.length; i  )
    {
        for (int j=i; j<a.length; j  )
        {
            int c = f(a, i, j);
            if (c%2 == 0)
            {
                if (j-i 1 > temp)
                    temp = j-i 1;
            }
        }
    }
    return temp;
}

CodePudding user response：

Time Complexity give high level estimate that how much time it takes to execute. So Yes you need to include every line of code which take time i.e time complexity of f function also. It is also take time.

What function has two loops and and one loop inside f function which is being called from what function.

Let calculate Time Complexity

Time complexity of f function when it is being first time from `what' function when i=0 and j incremented by inner loop from 0 to n

      1. When i=0 and j=0 then execute one time 
      2. when i=0 and j=1 then execute two time
      3. when i=0 and j=2 then execute three time
soon on 
      .
      .
      .
      n. When i=0 and j=n then  execute n time

SO
 Total = 1  2 3 4....... n
       = n(n 1)/2 = sum of n consecutive numbers

Thus

    TC of `f` Function execute first time from J loop from 0 t0 n =n(n 1)/2

But i loop execute n times so

Total Time Complexity of whole execution/ your program equalvent to n*[n*(n 1)/2] ~ n((n^2 n)/2) ~ (n^3 n^2)/2 that means TC equlavent to O(n^3)

CodePudding user response：

First of all, there is no n in the problem, so you cannot express the complexity as some function of n unless you define it.

Clearly, the function f takes time proportional to high-low 1. It gets called in the inner loop of what for low=i and all high in [i, l) [l:= a.length]. So the cost of this loop is proportional to 1 2 ... l-i = (l-i)(l-i 1)/2, which is a quadratic polynomial in l-i.

Finally, the outer loop repeats this for all i in [0,l), i.e. l-i in [1,l), resulting in a complexity ~l³/6.

CodePudding user response：

Yes, of course. Otherwise you could put the inner loop into a separate function and "magically" make your what function faster. Obviously that won't happen.