Big O runtime for this algorithm?

Question

Here's the pseudocode:

Baz(A) {
    big = −∞
    for i = 1 to length(A)
        for j = 1 to length(A) - i + 1
            sum = 0
            for k = j to j + i - 1
                sum = sum + A(k)
            if sum > big
                big = sum
    return big

So line 3 will be O(n) (n being the length of the array, A) I'm not sure what line 4 would be...I know it decreases by 1 each time it is run, because i will increase. and I can't get line 6 without getting line 4...

All help is appreciated, thanks in advance.

Answer 1

Let us first understand how first two for loops work

for i = 1 to length(A)
        for j = 1 to length(A) - i + 1

First for loop will run from 1 to n(length of Array A) and the second for loop will depend on value of i. SO when i = 1 second for loop will run for n times..When i increments to 2 your second for loop will run for (n-1) time ..so it will go on till 1.

So your second for loop will run as follows:

n + (n - 1) + (n - 2) + (n - 3) + .... + 1 times...

You can use following formula: sum(1 to n) = N * (N + 1) / 2 which gives (N^2 + N)/2 So we have Big oh for these two loops as

O(n^2) (Big Oh of n square )

Now let us consider third loop also...

Your third for loop looks like this

for k = j to j + i - 1

But this actually means,

for k = 0 to i - 1 (you are just shifting the range of values by adding/subtracting j but number of times the loop should run will not change, as difference remains same)

So your third loop will run from 0 to 1(value of i) for first n iterations of second loop then it will run from 0 to 2(value of i) for first (n - 1) iterations of second loop and so on..

So you get:

n + 2(n-1) + 3(n-2) + 4(n-3)..... 

= n + 2n - 2 + 3n - 6 + 4n - 12 + ....

= n(1 + 2 + 3 + 4....) - (addition of some numbers but this can not be greater than n^2)

= `N(N(N+1)/2)`

= O(N^3)

So your time complexity will be N^3 (Big Oh of n cube)

Hope this helps!

Answer 2

Methodically, you can follow the steps using Sigma Notation:

Answer 3

Baz(A):
    big = −∞
    for i = 1 to length(A)
        for j = 1 to length(A) - i + 1
            sum = 0
            for k = j to j + i - 1
                sum = sum + A(k)
            if sum > big
                big = sum
    return big

For Big-O, you need to look for the worst scenario

Also the easiest way to find the Big-O is to look into most important parts of the algorithm, it can be loops or recursion

So we have this part of the algorithm consisting of loops

for i = 1 to length(A)
    for j = 1 to length(A) - i + 1
        for k = j to j + i - 1
            sum = sum + A(k)

We have,

SUM { SUM { i } for j = 1 to n-i+1 } for i = 1 to n

= 1/6 n (n+1) (n+2)

= (1/6 n^2 + 1/6 n) (n + 2) 

= 1/6 n^3 + 2/6 2 n^2 + 1/6 n^2 + 2/6 n

= 1/6 n^3 + 3/6 2 n^2 + 2/6 n

= 1/6 n^3 + 1/2 2 n^2 + 1/3 n

T(n) ~ O(n^3)