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

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

Relational Databases

Relational databases are, well... a collection of data items that have relations between them. These relations are made by associating a one table's primary key with another table's foreign key. It is a great advancement from the old long table that was used to store data which was inefficient in terms of search, memory and space.  And as for normalization; it means a process in which tables are structured to eliminate redundancy and repetition among data and the CRUD operations side-effects. And as a direct result we improve the performance of our queries. An example of a relational database would be two tables; one for student and the other for school. Both of these tables have a column for the school id, and so we make a connection between by assigning the first one as a primary key and the other as foreign key.
Post a Comment
Read more