Question

Analyze each line of this brute force code and show that it is Θ(n3)?Please for each line.. especially the inner for loops.

void bruteForce_n3(int A[], int N, int& bestStart, int& bestEnd, int& bestSum) {
   int current = 0; //to hold current sum with every iteration.
   bestSum = INT_MIN;
   bestStart = 0;
   bestEnd = 0;
   for (int i = 0; i < N; i++) {
       for (int j = i; j < N; j++) {
           current = 0;
           for (int k = i; k <= j; k++)
               current += A[k];
           if (current >= bestSum) {
                   bestSum = current;
                   bestStart = i;
                   bestEnd = j;
           }
       }
   }
}

Answer 1

Lines above for loop will take constant amount od time. It is clearly seen from the algo. most outer for loop will run 'n' times while the inner loop will depend on the value of i. So it will run as

N times + (N-1) times + (N-2) times +..+ 1 time = N(N+1)/2 = O(N^2).

Now, the most inner loop is depending on the value of i and j. So, for i=0, j will go through 0 to N-1; and k will run 1 times+ 2 times +..+N-1 times = O(N^2) times.

Similarly, for i=1, j will go through 1 to N-1 times. So, k will run 1 times+ 2 times +..+N-1 times = O(N^2) times.

And it will continue upto N values. So, in overall results in O(N^3). And statements after loop will take constant amount of time.

So, in overall time complexity of given algo. will be O(N^3).