DEV Community

Cover image for Intro to  Big O Notation 👀
Sai gowtham
Sai gowtham

Posted on • Updated on • Originally published at reactgo.com

Intro to Big O Notation 👀

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 Paul Bachmann, Edmund Landau.

Let's discuss some common time complexities with the help of examples.

Constant time O(1)

If an algorithm has a constant time, it means that it always takes the same amount time to produce the output.

Example

function removeLastitem(arr){
  return arr.pop()
}

console.log(removeLastitem([1,2,3,4,5,6]))
Enter fullscreen mode Exit fullscreen mode

In the above example removeLastitem function always takes the same amount of time to remove the last item from the array it doesn't matter if the array has 10 items or 20 items.

Linear time O(n)

if an algorithm has a linear time, it means that the running time of an algorithm grows as the input size grows.

example

function sum(arr) {
    let total = 0;
    for (let i = 0; i < arr.length; i = i + 1) {
        total += arr[i];
    }
    return total;
}

console.log(sum([1, 2, 3, 4])) //10
Enter fullscreen mode Exit fullscreen mode

In the above example,sum function increases its running time according to the size of the array.

Quadratic time O(n2)

The running time of an algorithm is directly proportional to the square of the size of the input.

example :

function addAndLog(arr) {
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr.length; j++) {
            console.log(arr[i] + arr[j])
        }//O(n)
        console.log("----")
    }// O(n)
}
Enter fullscreen mode Exit fullscreen mode

In the next tutorial, we will learn about logarithms hope you learned something.

Happy coding ...

Follow me on twitter

Originally published at reactgo.com

Top comments (13)

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
 
sait profile image
Sai gowtham

Updated

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.

Collapse
 
antoinebr profile image
Antoinebr

Looking forward to read the next tuts ! 👍

Collapse
 
sait profile image
Sai gowtham

checkout next tutorial .

Collapse
 
theredspy15 profile image
Hunter Drum

Best intro I've seen to the Big O!

Well done!

Collapse
 
mshel profile image
MikhailShel • 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(n2). That's critical. Any constants in Big O notation can be dropped

Collapse
 
sait profile image
Sai gowtham

Updated

Collapse
 
diek profile image
diek

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

Collapse
 
sait profile image
Sai gowtham

checkout Logarithms

Collapse
 
theoutlander profile image
Nick Karnik • 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!!