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

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

Greenfield Project

This is a project where me and other three people joined forces to build it together. It started with meeting each other on the first day to decide on the project idea. After a couple hours of brainstorming we finally decided on a particular thing to do; and it was a web app to help manage a school system. This app was aimed at teachers, parents and students, in addition to admins moderating the system. We started big and worked our way through the waffle tasks but got overwhelmed along the way since it was a very big project for both our limited time and our team members' technical abilities. We faced many difficulties while working on this project; especially setting up mysql and getting it to work on all of our team members' machines. We switched to setting it up locally because the website we used to host our database kept showing an error of too many users so we kept testing locally until we hosted it online on a different website before the end of the time period. We work...
Post a Comment
Read more