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.

Accepted Answer

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!

Big O runtime for this algorithm?

Solution

Problem