DEV Community

Intro to Big O Notation 👀

Sai gowtham on October 03, 2018

What is Big O? In computer science, big O is used to analyze how their running time or the space used by an algorithm.it is invented by ...

Read full post

Thibaut Rousseau • Oct 4 '18

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)

Sai gowtham • Oct 4 '18

Updated

Ali • Oct 5 '18

O(10 *n) how ?

Can you explain please !

Thibaut Rousseau • Oct 5 '18

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.

Antoinebr • Oct 3 '18

Looking forward to read the next tuts ! 👍

Sai gowtham • Oct 4 '18

checkout next tutorial .

MikhailShel • Oct 4 '18 • Edited

the last example should have
for (var j = 1; j <= n; j++) {
or
for (var j = 1; j <= i; j++) {
for 2'd loop

to be O(n^2). That's critical. Any constants in Big O notation can be dropped

Sai gowtham • Oct 4 '18

Updated

diek • Oct 4 '18

Ouch, logarithms one were the content I was looking for when I entered here, I hope you will post it soon.

Sai gowtham • Oct 4 '18

checkout Logarithms

Nick Karnik • Oct 3 '18 • Edited

It would be nice if you could expand a bit on this topic since there's more to it.

The Big-O Cheat Sheet is nice, especially that poster!!