DEV Community

loading...

Discussion on: Intro to Big O Notation 👀

Collapse
thiht profile image
Thibaut Rousseau

The last example doesn't look quadratic to me but linear, because the second loop is executed a fixed number of times. Its complexity would be O(10 * n), which is proportional to O(n)

Collapse
malib profile image
Ali

O(10 *n) how ?

Can you explain please !

Collapse
thiht profile image
Thibaut Rousseau

The author fixed it, but the code used to be something like:

for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < 10; j++) {
        console.log(arr[i] + arr[j])
    }
}

The console.log statement is executed arr.length * 10 times. That's a complexity of O(10* n), n being the size of the arr array.

Thread Thread
t0nyba11 profile image
Tony B

Just to be painfully anal, there is no such thing as O(10*n). Constants disappear in Big-O notation as it is only concerned with growth rates and limiting behavior, not the actual time taken for a certain operation. i.e. your example it is still O(n).

Collapse
sait profile image