 # What is the runtime of my algorithm? O(n) or O(n^2) - I am a little confused

I am working through a Udemy algorithms and data structures course after completing the course on Codecademy. I have learnt big O notation but am still not that confident with the subject,

I just solved the following code challenge:

Write a function called maxSubArray which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array. For example:

`maxSubArray([1,2,5,2,8,1,5], 2) // Return 10`
`maxSubArray([1,2,5,2,8,1,5], 4) // Return 17`
`maxSubArray([1,2,3,4,5,6], 1) // Return 6`

This is my solution:

``````function maxSubArray(arr, n) {
let maxSum = arr;
let temp;

// Check n is not greater than array length.
if (n > arr.length) return null;

// Loop over each element within array.
for (let i = 0; i < arr.length - n + 1; i++) {
temp = 0;

for (let j = 0; j < n; j++ ) {
// Temp is equal to temp + element.
temp = temp + arr[j + i];
}

// If temp is greater than maxSum, update maxSum to value in temp.
if (temp > maxSum) maxSum = temp;
}

return maxSum;
}
``````

Although I have two nested loops which I know is normally a dead give away of a quadratic runtime, my second loop will only run n number of times? If my array is of length 5 and n is 2 surely my operations are O(10) → O(n)? If it were quadratic and not linear, surely the number of operations would be 25, assuming length was still 5? The video I watched describes the above approach as having a quadratic runtime.

Thank you ( 1 Like

Hi,

Let’s break it apart. First loop runs `arr.length-(n+1)` times, let’s call that `a` (it’s not quite n yet, even if we choose to simplify it later). Then, the second loop runs `n * a` times. The question is really about how this runs as it scales up, and maybe there is an interest in seeing if there’s a closer approximation (as different expected array lengths and n’s may make a difference, before we know the math).

So let’s try some examples:
Array length 10, n = 2 → a = 9, it will run `9 * 2 = 18` times… this seems nice.
Array length 10, n = 5 → a = 6, it will run `6 * 5 = 30` times… hm, closer to n^2.
Array length 100, n = 5 → a = 96, it will run `96 * 5 = 480` times… aha, so it’s not really n^2 is it? It seems to vary… but how can we think of that constructively?

So my thought is that it would by `n * a` run time when n is small, where `a` is the size of the array. (Medium case? depends on context). Best case n is big in comparison to the array size. Notice, if a = 100 and n = 100, that’s just 1 * 100 = 100. Or a run time of `a`. We usually don’t care about best edge case for this type of analysis though. It’s only truly n^2 when n is about half the size of the array. So I think knowing the expected inputs in context would add an important wrinkle to this. But it is correct to say n^2 runtime because that’s what it is for worst case. Without context, one assumes worst case.

Which means that the for-loop short-hand for n^2 run time only works when the size of the loops are both n. If they’re 2 independent variables then it can’t be n^2, but rather n * x (whatever you want to call the 2nd variable). Why make the distinction? Because context sometimes means that certain inefficiencies won’t come to light (hashmaps are a good example of a worst-case being discarded because of context).

For testing you can put a log statement on your inner loop with a counter. Invoke the function with an empty array like `maxSubArray(Array(100),5)`

Anyways, that’s my superficial reading of this… let me know if I made any oversights.

I find the discrete math lectures that MIT opencourseware provides (free) give a great foundation for the preparatory math for Big O analysis. Their algorithm classes also go into beautiful detail but I think it’s good to have discrete concepts at least somewhat fresh before jumping into the thorny stuff.

5 Likes

This is a hint:

``````const items = [1,1,1,1,2,1,1,1,1,1,1,1];
const n = 3;
var max = 0;

for (let i = 0; i < items.length - n; i++) {
let batch = items.slice(i, i + n);
if (batch.length < n) {
break;
}

let total = batch.reduce((total, current) => { return total + current; });
max = total > max ? total : max;
}

console.log(max)
``````

Sorry for such the late reply!

Thank you for such a detailed explanation, I really appreciate it and now have a much better understanding!

1 Like