The Startup
Published in

The Startup

Simplifying Big O Expressions

When describing the time complexity of an algorithm, there are some rules to simplifying Big O expressions. If you want to see how to calculate operations for Big O notation qualifications; You can read my my previous blog about Big O Notation and Algorithm Analysis with JavaScript Examples .

Let’s make a quick recap; Based on exact number; The number of operations grows approximately with n. If (n) doubles the number of operations also doubles base on (n).

You can run it over an array of (5) items and it will run pretty quickly, but if you ran it over an array of (10,000) items then the execution time will be much slower base on example of a for loop.

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

O(n): Constant does not matter , If we have O(2n) we simplify it’s as O(n)

O(1): If we have O(500) we just simplify that O(1). We are just saying here that we have 500 operations every time no matter what is the (n)

O(n2): If our graph goes to infinity we are just looking at the difference between(13n2) and just (100n2) they all gonna look similar.

So we can write them to format which I described above. So we know that O(1) is faster than O(n) . O(n2) would be slowest.

Smaller term also like this O(n+10) & O(1000n+50) simplify as O(n). Because we don’t need constant and smaller terms on the end.

For O(n2+5n+8) If we look big picture 5n+8 meaningless to compare(n2) so we simplified that as O(n2).

I know analyzing complexity with Big O can very complicated. There are some rules but those rules won’t always work itself. But they are helpful in the beginning to understand to flow of Big O!

  1. Arithmetic operations are constant ( adding , subtracting, dividing takes constant time value of the number really doesn’t matter)
  2. Variable assignment is also constant( Computer takes same amount of the time for example var x = 3000 or var x =300000
  3. Accessing elements in an array (by index, or an object(by key) is constant(if I have an array and I find second or tenth item as long as I use index its takes constant time)
  4. In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop( Let’s say; We have a loop in array which has 100 item in it, when (n) grows operations also grows based of (n). What ever happens inside that loop also consequential. If we have nested loop we ended up with squared run times)
Sources Colt Steele Js Algorithms and Data Structures Master Class
Sources Colt Steele Js Algorithms and Data Structures Master Class

Let’s have a function

I implemented a function called logAtleast5(n);

If I pass the logAtleast5(10) it will log 10 times if I pass logAtleast5(1) it will log one time. Its prints all number up to n and minumum prints 1,2,3,4,5.

function addUpTo(n){
return n * (n + 1) / 2;
}
console.log(addUpTo(3))let t1 = performance.now();
addUpTo(1000000000)
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1)/100} seconds.`)

What is the Big O here; How do I categorize it?

function logAtleast5(n){
for (var i = 1; i <= Math.max(5, n); i++){
console.log(i);
}
}

We have a loop and this loop is going from (1 )to either (5)or Which ever one is larger , We can worry about number ”5" (Math.max(5, n)in the loop. But We really cares about what happens if n grows larger.

If n grows till infinity What Will happen to run time?

If n(1000000), this loops going to run (1000000) number(5 ) not important (Math.max(5, n). We can simplify this as 0(n). Because (n) grows number of operations grows.

Let’s have another function exactly do opposite of first function. This function (log) max 5 times. If the number passed in more then (5), its still log 5 times.

function logAtleast5(n){
for (var i = 1; i <= Math.min(5, n); i++){
console.log(i);
}
}

If n grows here it does not really matter. Because we will take to Math.min in this function.

for (var i = 1; i <= Math.min(5, n); i++){

Even if the n is (1000), loops just run just 5 times. If n (2) loops runs 2 times. Graph would actually stay static till (5). We can simplify n constant as O(1)

Sources Colt Steele Js Algorithms and Data Structures Master Class

As We see general chart like this . We can see 0(1) is flat one. This is great if we have 0(1) run time. Because it’s perfect constant run time. O(n) its not bad. It is much better than quadratic or squared run time. But o(n2) definitely slowest one. I know it’s very complicated but as I mentioned above; When you see o(n2) and you can understand what is the Big O classification. It’s more than enough for now. We almost go over all basic of Big O notation classification in this article. Thank you for your time…

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Soner Mezgitci

Soner Mezgitci

Software Engineer | Ruby on Rails | JavaScript | HTML5 | CSS | PostgreSQL | React | Redux