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 (:grinning:

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