DEV Community

Cover image for The Big O Notation - An Introduction

The Big O Notation - An Introduction

Sarah Chima on August 05, 2019

You might wonder why I added a picture of a blue alien as my cover image. It's a character from one of my favourite movies "Home" and his name is O...
Collapse
 
stealthmusic profile image
Jan Wedel

Thanks for this article, those are good and easy examples!

Still, because you mentioned it, I wonder if I would just walk out the room if sometimes someone asks me about big O notation in a job interview.

Not because I don’t understand it, but because I’ve never needed it a single time in the last 20 years.

Collapse
 
havarem profile image
André Jacques

I once was asked to reduce the execution time of a MySQL procedure. That query could take between 2 to 3 minutes to execute using a recursion-ish call that could, at worst, make it an O(n^3). My solution was to change the data structure, which was very strange, to a JSON one and use the Generated Column feature, we could reduce to an O(n^2) for the procedure and the time was at the 10ms. The only drawback was a little increase in insertion time.

I don't think people say "hey look, this triple-loop through all the dataset is an O(n^3)", you just know something is wrong and go up to a better solution right away.

Last but not least, knowing the kind of task you want to do with the data, how it will be managed, grow and access can help you select the proper type of data structure, may it be a set, a queue, a stack, a linked list, etc.

Collapse
 
jennrmillerdev profile image
Jen Miller

It depends on the job though. I do Java backend transaction processing so our team always needs to understand a basic understanding of runtime (and memory usage) when we code. It's mostly basic things like why something is 'faster' then O(n2). Sometimes to reduce runtime, we cache, but then we have to consider the size of the cache, etc

That being said, for front-end web dev, I don't think I've ever had to ever think about it.

Collapse
 
stealthmusic profile image
Jan Wedel

Yes, I think the key point is that after some good or bad experiences, most developers will have an implicit knowledge that helps deciding on how to program something and when something’s very slow to find out why.

That said, I’ve probably used it a lot of times. But I never wrote down or talked explicitly about O().

And by the way, I was a java Backend developer for most of my time and just recently started in the frontend as well.

Collapse
 
rockykev profile image
Rocky Kev

I ask this to senior devs pretty frequently, about how often they use Big O. They respond like you. I asked because I still struggle with learning it.

I think about that time I build a reporting tool in python, and it took 50 seconds to compile the report. I was still learning, and the thing worked so :shrug:.

Now that I 'sort' of understand Big O- if I had to refactor that code, I'm more likely to think about performance and when to use specific loops/nested loops.

I still won't be able to go, "AH - that's a O(n log n)" or whatever. But that background understanding does change how I will approach the problem.

Collapse
 
valericaplesu profile image
Valerica Plesu

true :)

Collapse
 
ndiecodes profile image
Ndifreke Friday

Awesome article, Sarah!

Collapse
 
sarah_chima profile image
Sarah Chima

Thanks Friday

Collapse
 
dubem profile image
Dubem

great article, sarah!

might i add, 'grokking algorithms by aditya bhargava' is a great resource for getting up to speed with big o notation and algorithms in general (when and which to use).

github repo containing algorithms in different languages from grokking's masterpiece: github.com/egonSchiele/grokking_al...

Collapse
 
jesuskidz profile image
Ola Popoola

Thank you for this useful information. Just placed an order for the book. It's exactly what I needed.

Collapse
 
gooch profile image
Anthony Ghilarducci

Great overview, although re: O(n log n) it may be worth noting that complexity is the average time complexity for most sorting algorithms as best and worst can range from O(n) to O(n2) for many of them.

Collapse
 
sebbdk profile image
Sebastian Vargr

I rarely use big o notation, but it is solid knowledge to have since it makes us think about function complexity and the cost’ around things like disk io, or something silly like asking a html element about its dimensions.

In that context, i find it remarkably relevant.

Collapse
 
devpablofeijo profile image
Pablo Ruan

Nice article! Thank you Sarah :D

Collapse
 
sarah_chima profile image
Sarah Chima

Thank you Pablo

Collapse
 
sarah_chima profile image
Sarah Chima

Thank you

Collapse
 
niyasrahman profile image
niyasrahman

Thanks For this article

Collapse
 
sarah_chima profile image
Sarah Chima

Thanks for reading it. I'm glad you like it.

Collapse
 
karthikrangaraju profile image
Vengada Karthik Rangaraju

Could you give an example for O(n!) kind of felt like it wasn’t explained well enough..👍 for the rest of them :)

Collapse
 
beugenio profile image
Bruno Eugênio

Very nice article, Sarah!

Collapse
 
sarah_chima profile image
Sarah Chima

Thank you Bruno

Collapse
 
dr_dimaka profile image
Dmitry Pavlov

A bit easier way to explain #BigONotation :)
twitter.com/dr_dimaka/status/11555...

Collapse
 
rockykev profile image
Rocky Kev
Pranay Pathole @PPathole · Jul 28
Alternative Big O notations: 

O(1) = O(yeah)

O(log n) = O(nice)

O(nlogn) = O(k-ish)

O(n) = O(ok)

O(n²) = O(my)

O(2ⁿ) = O(no)

O(n^n) = O(fuck)

O(n!) = O(mg!)
Enter fullscreen mode Exit fullscreen mode

LOL!

Collapse
 
ebenoladutemu profile image
Ebenezer Oladutemu • Edited

Immediately I saw the topic, Oh the Boov came to mind and I mentioned his name. Opening the link then seeing him gave me joy!😂😂. My best animation yet! Amazing helpful post! Learnt more.😊