DEV Community

Cover image for Big O notation basics made dead simple

Big O notation basics made dead simple

JTK on September 02, 2022

A brief conversation about big O To be honest with you, when I first got into programming I procrastinated learning Big O for quite a wh...
Read full post
Collapse
 
canolcer profile image
Can Olcer • • Edited

Great post! Not sure if I'm getting something wrong, but in your object example, should't it be like this

// Example: given target number 8 and list [1,2,3,4,9,6] my JS object would
// look like this:
{
   7: 0, 
   6: 1, 
   5: 2, 
   4: 3, // this shouldn't have any index (-1 maybe?) because it's larger than 8
   6: 5 // shouldn't this be 3: 4 ?
}
Enter fullscreen mode Exit fullscreen mode

Also, in your code what happens if targetNum < list[i] (this would happen in your given example array above [1,2,3,4,9,6] and target number 8) on line 28:

differenceAndIndex[targetNum - list[i]] = i;
Enter fullscreen mode Exit fullscreen mode
Collapse
 
heyjtk profile image
JTK •

I'm not sure if I am getting your question but will return to it later, I'm not sure if I am seeing the behavior you mention running that example though? Screenshot below...will try to remember to revisit this and get back to you later on
Image description

Collapse
 
canolcer profile image
Can Olcer •

I think it's correct in your code, but wrong in the example you have given. And with my comment regarding line 28 I was referring to the second (optimized) version of the code. So, not the screenshot you posted as a reply, but the next one.

Collapse
 
hypnoglow profile image
Igor Zibarev • • Edited

Great article, thanks!

Regarding the code challenge example, keep in mind that the solution with hash map requires M(n) additional memory, while the O(n^2) solution requires M(1) memory. So this is a trade-off; there might be cases where it would not be possible to fit all the data in memory, and you would have to use the algorithm that is less effective in terms of CPU.

Collapse
 
heyjtk profile image
JTK •

Writing this for new people, I chose to skip memory entirely in introducing the concepts since in my (long) career I have so relatively rarely hit space vs time constraints. Appreciate this point, but definitely was deliberate to skip some finer points in this which was written for pure newbies :) (actually originally wrote it for some mentees who are a few months into learning to code)

Collapse
 
martinhaeusler profile image
Martin Häusler •

@citizen428 I thought of this immediately when I saw the post, you beat me to the punch ;) It's so good.

Collapse
 
heyjtk profile image
JTK •

Oh my god I love this haha!

Collapse
 
kalamees21 profile image
Mikk Laos •

Thanks

Collapse
 
user_661ff24093 profile image
user_661ff24093 •

Great job! Thanks a lot for this!

Collapse
 
benjamindelpech profile image
benjamin DELPECH •

Really well explained, thanks you

Collapse
 
oldjavaguy profile image
❄ Sean P. Floyd ❄ •

Am I missing something? The quadratic example given seems linear to me. If there are 5 tasks in each house, 5 is a constant, so the complexity is O(5N) which is considered equal to O(N). That N happens to be 5 in the example is irrelevant.

It would be O(N^2) if the number of tasks grew with the number of houses (e.g. 1 task per house if there is only one house, but 5 tasks per house if there are 5 houses, i.e. f(1)=1 and f(5)=25).

Collapse
 
nildaranki profile image
NildaRanki •

What are the rule of using Big O notation? كيفية جلب حبيب