# What’s Big O notation, faster runtime — Simply explained

# What’s the Idea of Big O?

How do we know how fast our algorithm runs? that’s where Big O Notation comes in. Let’s take a look at how google defines it:

A theoretical

measureof theexecution of an algorithm, usuallythe time or memory needed,given the problem size n, which is usually the number of items. Informally, saying some equation f(n) =O(g(n)) means it is less than some constant multiple of g(n).

Instead of evaluating our code with words like, “ great”, “meh” or “awful”, we can have a numeric representation to evaluate our code performance.

It might look a little bit mathematical, but once you grasp the concept, it gets easier to learn along the way!

# Why We Care?

Why do we even care about which algorithm is the best? Shouldn’t the best solution be the one that it works? True, but what if we are working with a huge data set?

- When one algorithm can save hours in comparison to the other; it is important to have a way for us to formally talk about our code performance.

2. There are so many ways to solve the same problem, Big O discussion is useful to talk about trade-offs among various problem solving approaches.

3. It also helps us to understand when we are debugging, because knowing how runtime works will assist us to identify inefficient code in our applications.

4. Probably less important reason, but it comes up in interviews a *lot*!

# Let’s Bring Up Two Functions to Compare

Suppose we want to write a function that gets the sum of all numbers from 1 up to some number n in Javascript. Let’s take a look at the following two functions.

Both functions do exactly the same thing but one is less intuitive, yep some math magic on the second one!

There’s math behind how we arrived to the second function, but this is not the main focus of this blog, so I will not get into deeper discussion on it. Let’s continue with the main focus which is evaluating and comparing these two pieces of code.

We could probably compare these two functions by measuring the runtime.

But, probably not the best way…

What’s the problem if we use time to measure how fast the code can run?Well, different computers will record different times and/ or measurement may not be precise enough.

How do we know which code is better?

Let’s try to count the number of operations! let’s take a look at the simple operation with the short line of code:

function addUpTo(n) {return n * (n + 1)/2;}

1 multiplication, 1 addition, 1 division. So regardless of size of n, we have 3 simple operations here. Let’s look at the first one:

function addUpTo(n) {let total = 0;for (let i = 1; i<= n; i++){ total += i;

}

}

It’s not just one operation, it’s n additions and assignments on this function. when we look at i++, there’s additions and assignments. it’s n additions and n assignments as the size n grow.

Counting is just hard! As n grows the number of operations grows in correlation with n.

# Introduce Big O

Big o is just a way to formalize complex counting!

It gives us a formal way of talking about runtime of algorithms grows as the input grows! Here’s the trend.

**f(n) as output; n as input.**

`f(n) could be linear `**f(n) = n **

as n (input) scales , the f(n) (runtime) scales as well.

`f(n) could be quadratic `**f(n) = n^²**

as n (input) grows, the f(n) runtime squares.

`f(n) could be constant `**f(n) = 1**

as n (input) grows, it doesn’t have any impact on runtime f(n) because runtime is always constant, which can be simplified to 1.

# Bottom Line

Here are the gist of this blog:

When we talk about Big O we talk about the wrost case scenario, the upper bound of runtime.

As n grows , It’s reflected in the run time.

lets get back to our examples earlier:

function addUpTo(n) {return n * (n + 1)/2;}

The trend is having a Big O of 1 **O(1) , **it’s telling us that as input of the function grows, the runtime is not reflected.

In comparison to the second one,

function addUpTo(n) {let total = 0;for (let i = 1; i<= n; i++){total += i;

}

}

there are a tons of operations happening, number operations is eventually bounced by a multiple of n, say 10n.

One thing we want to emphasis is that, we don’t care of weather is 5n or 10n. Essentially they are the the same when we charted it in a massive chart with a large size of input. We only concern about the order of latitude in the graph, in order words, we care just in a fussy way!

I hope this article help to clarify the concept on Big O notation. This article is inspired by one of my favorite udemy instructor, Colt Steele, his course is called JavaScript Algorithems and Data Structures Masterclass