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;} `

## 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)

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)

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…

--

--

## More from The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +760K followers.

## Get the Medium app

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