1

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;
}
khelwood
  • 55,782
  • 14
  • 81
  • 108
Dima Tkachuk
  • 25
  • 4
  • 3
    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. – Konrad Rudolph Dec 13 '22 at 11:55
  • I am complete noob in algorithm complexity estimation but Are you sure your `what` has O(n^2) ? There is still inner loop that shifts start position every outer loop iteration. – Alexey R. Dec 13 '22 at 11:57
  • 1
    @AlexeyR. yes it's O(n^2) : `n + (n-1) + .. + 2 + 1 = (n+1)n/2` [here's an answer](https://stackoverflow.com/questions/2483918/what-is-the-proof-of-of-n-1-n-2-n-3-1-nn-1-2) – Alois Christen Dec 13 '22 at 12:03
  • @AloisChristen: this is plain wrong. –  Dec 13 '22 at 13:42
  • @YvesDaoust how so ? could you elaborate where it's wrong ? I'm talking about the `what` function only, without the added complexity of the `f` function. – Alois Christen Dec 13 '22 at 14:00
  • @AloisChristen: without the added complexity ??? `f` is called, you can't ignore it. –  Dec 13 '22 at 14:03
  • You *can* express time complexity in terms of function calls to `f`, if explicit about it. The helper function can be viewed as a black box / oracle, and it can be useful especially if we don't know its complexity or if it might vary. – Berthur Dec 13 '22 at 16:02

1 Answers1

3

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-1)n)/2) + ((n-2)(n-1))/2+ ...... + 1] ~ that means TC equlavent to O(n^3)

Pradeep Kumar
  • 1,193
  • 1
  • 9
  • 21