# 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[0];
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