DEV Community

Comprehensive Big O Notation Guide in Plain English, using Javascript

Şahin Arslan on April 04, 2021

If you are a Computer Science student or graduate, it is 100% safe to assume this is a subject you absolutely know about. But if you are currently...

Read full post

Dada David Oloruntofunmi • Apr 8 '21

This is really good.... really really nice thanks so much...
Sharing right away

Buh please can anyone recommend a site for me to learn algorithm and Data structure.. like a toturial Pls

Am a newbie to computer science 🙃🤠

I would really appreciate

Shalom

Şahin Arslan • Apr 8 '21 • Edited

Hey Dada David, thanks!

There are plenty of resources for learning Data structure and Algorithms. I think choosing a learning platform or teacher is a personal matter. Personally I don't settle down with only one resource, I like to check through different ones to see different angles. My recommendation would be to research further until you find a resource (or resources) that speaks to you with the way of explaining the subjects.

Emma Bostian ✨ • May 3 '21

I wrote a book about it! technicalinterviews.dev/

Mamane Bello • Apr 8 '21

Check algoexpert of Clement it's a good one

Ferit Tunçer • Apr 6 '21

Great article. But you are, like most authors writing in this topic, missing one important point. All the complexity analysis is based on selection of a basic operation. And depending on this basic operation preference, resulting complexity might greatly differ. See my old answer and the discussion on SO: stackoverflow.com/a/34749542/1079908

Şahin Arslan • Apr 6 '21 • Edited

Hey Ferit,

Thanks for your feedback and interesting input! I'd like to point out my main idea of writing this article. I had 2 primary type of readers in mind: either someone encounters Big O for the first time, or someone needs to refresh their memory. I wanted to put comprehensive emphasis on the main parts while keeping it as simple as possible.

I have also considered diving into the details of complexity analysis as well. But I have realized something. If I also include them, it won't be an article for beginners first ride or a memory refresher anymore. It would be unfair if I expect a beginner to understand Big O and it's complexities, then be able to make detailed analysis at the end of a single article.

That's why I decided to spare complexity analysis part for another article instead. I will be updating this article with a link to it when it is ready.

Steve Huckle • Apr 8 '21

I'm quite certain that was obvious from the tone of the article, but thanks for clarifying...

Ferit Tunçer • Apr 7 '21

Oh, that explains. Thanks for the answer and looking forward to the next article!

'Seun Somefun • Apr 8 '21

Very great article and explanation. One of the best so far.Quick question how are shift() and unshift() linear runtime complexities?

Şahin Arslan • Apr 8 '21 • Edited

Hey Oluwaseun, thanks!

Great question. To be able to make a comparison, let's take a look at push() and pop() methods first:

push() - Adds an item at the end of an array
pop() - Removes an item from the end of an array

They don't need to iterate whole array to make these changes, they only need to operate with one element with a known index - last one.
Previous indexes inside the array does not getting effected by this change.
That's why both are these having O(1) - Constant time complexity.

Now let's think about how shift() and unshift() operates:

shift() - Removes an item from the beginning of an array
unshift() - Adds an item or items from the beginning of an array.

Even they also target a known index, they work different. Because mutation takes place at the beginning of an array, which causes an index change for all other elements coming after. Let's take shift() for an example:

const array1 = [ 'a', 'b', 'c' ]

const firstElement = array1.shift()

console.log(firstElement) => Output: 'a'
console.log(array1) => Output: ['b', 'c']

You see, before shift(), 'b' was at index[1] and 'c' was at index[2].
Now their indexes have changed to index[0] and index[1] respectively.

Therefore we can say runtime to operate an index shift is directly linked to the length of array, so these methods are having Linear runtime complexity.

But again, you will find the perfect accurate answer by reading the source code of Javascript Engine you are dealing with, which is often V8:

github.com/v8/v8/blob/master/src/o...

Mackenzie • Apr 9 '21

And this is where the distinction in memory between an array and a linked list comes in, I suppose, because sticking something on the front of a linked list should be constant like the push & pop. (Meanwhile, accessing within a linked list is linear.)

'Seun Somefun • Apr 8 '21

Oh so what makes shift() and unshift() O(n) is because of the change in the index they cause for elements in the array and not because they affect a single element at a known index?

Şahin Arslan • Apr 8 '21

Yes, main reason is mutation place: beginning of an array. Adding or removing an element from start changes index order of all other elements coming after it.

'Seun Somefun • Apr 8 '21

Thanks Sahin

Celeste • Apr 29 '21

this is a super important point :-) thanks!

Ashley Oliver • May 4 '21

Nice article, but one criticism. Unless the intent is to confuse the non-mathematical do not mix "38% faster" and "40 times faster" in the same sentence. Indeed, you have confused yourself. You did not mean "38% faster" you meant "ran in 38% of the time" which I would interpret as 263% of the speed or 163% faster.

Şahin Arslan • May 31 '21

Hi Ashley,

Thanks! I really appreciate your feedback, you have a solid point. Now I have updated the part accordingly. I will be sticking with the "times faster" way of explaining, I believe we can safely interpret 263% of the speed as 2,6 times faster here.

Rohit Gupta • Apr 7 '21

This is great. Sharing this on linkedIn right away. :)

Mackenzie • Apr 9 '21

Thanks for this. Occasionally self-taught devs ask me for resources on formal CS stuff, and I'm bookmarking this for next time.

Şahin Arslan • Apr 9 '21

Hey Mackenzie, your welcome. Glad to hear!

Abdullah • Apr 7 '21

Thank you very much.

Emma Bostian ✨ • May 3 '21

Nice guide! If you're going to use images and graphics from other sources though you should credit them.

Şahin Arslan • May 3 '21 • Edited

Hey Emma!

Thanks for your feedback and also letting me know about the missing credit. I usually include the credits via using image alt tags, seems like the "Big O Graph" escaped my notice. Now the post is up to date with a visible link to it's resource 👍

bigocheatsheet.com is a great resource and definitely worth to keep it bookmarked!

Robin Bastiaan • Apr 8 '21

This makes me wonder; is there a complete list of js array functions with their corresponding complexity, so we can implement the best way of doing something?