Skip to main content

Big O Notation

Big O Notation is a mathematical expression that describes how much time an algorithm takes to run according to the size of it's inputs; mostly concerned about the worst case scenario.

Types:

1- Constant Time O(1):
On this order, regardless of the number of items, the iterations(time) are constant.

Example:
const getFirstItem = items =>
   items[0];

getFirstITem([1, 2, 3, 4]);  // 1 (one iteration)
getFirstItem(['b', 'd', 'g']);   // 'b' (one iteration)

2- Linear Time O(n):
On this order, the worst case grows with the number of items.

Example:
Javascript's built in function indexOf, it loops over an array to find the  correct index of the passed element. The worst case is looping over the whole array.

[1, 2, 4, 9, 23, 12].indexOf(12);

3- Quadratic Time O(n ^ 2):
For this order, the worst case time is the square of the number of inputs. It grows exponentially according to the number of inputs.

Example:
Using nested loops would be a good example, or using a loop with a built in function that loops over the elements like indexOf.

for(let i=0; i<arr.length; i++){
   if(arr.indexOf('j')){
    //do something
    }
}

4- Logarithmic Time O(log n):
These are the best for searching and sorting algorithms, they usually are most efficient when dealing with large collections. There's no need to look through the components one by one; but splitting the data to parts and discard some of them at every iteration.

Example:
Great examples on this includes merge sort, binary search and quick search.

Image result for binary search javascript

These are the most common of them, and as a conclusion I leave you with a chart that summarizes what we have talked about thus far.


Comments

Post a Comment

Popular posts from this blog

Middlewares

Middlewares in Javascript are functions that come in the middle of the request-response cycle. They have access to both the request and the response object as well as the next middleware function to be executed; usually called next(). Popular examples on middleware include: body-parser, cors, session, cookie-seesion and cookie-parser.
Post a Comment
Read more

Stack vs. Queue

Stack is like a pile of  books placed on top of each other. We can add new books to the top and can remove them from only the top because stacks are LIFO which means last-in, first-out. Queues on the other hand are the opposite, which is FIFO meaning first-in, first-out. So adding an element to the queue will be the same but removing will happen to the first element not the last one. An example of a queue would be the wait line in front of any kind of service we see around us like the bus station or the shops,....etc.
Post a Comment
Read more

How Does While Loop Work?

I think that everybody knows what while means, right? Imagine you want to do something for a 'while' :) You're gonna need to repeat that thing for a number of times; limited or unlimited. For example, if you wanted to do something from your daily life like drinking water 7 times each day you're going to do a task (i.e process) for seven times and you're going to decrease that number each time you drink water. Before you start drinking, the number of times would be seven. So,  a condition to check to stop drinking would be great. Like when the number of times is less than seven -> continue doing this process (drinking water) and increasing the number of times you have drank  by one. Once the number of times reaches seven -> stop this process. Hope that helped clear the picture even if it was a little bit.
Post a Comment
Read more