search

dlbrush / advent-of-code-2021

1 stars 0 forks source link

Avoid O(n^2) (Dear lord...did I just cite Big O time in a PR comment? Please shoot me). #1

Open dhempy opened 2 years ago

dhempy commented 2 years ago

https://github.com/dlbrush/advent-of-code-2021/blob/8cc9a24d2fd0f35b391120ad944ff76eacc51fe5/3/output2.js#L8

I don't think you have to nest these two loops.

I think you can loop through the line width once to initialize your column counts to zero.

Finish that loop, and then loop through all the lines, incrementing the counts in each position.

In fact, I'm confused how the current code doesn't reset all the counts back to zero every time it increments to the next row.

dhempy commented 2 years ago

Ah, my bad...even if you pull out all the initializers, you'll still be looping across each line while looping through all the lines, so...never mind...

dhempy commented 2 years ago

On the upside...this is not O(n^2), even though it looks like it with the nested loops. It's actually O(n * w), where w is the width of the input. Assuming the width doesn't scale up, we can call it a constant, so you're really running O(n), which is about as good as it gets.

And...wow...I can't believe I'm discussing Big O. I feel like a sophomore all over again.

dlbrush commented 2 years ago

Hahaha I graduated from bootcamp all of 1 week ago, so Big O is still on my mind constantly. This is a good point though, hadn't really thought about it that way. It would definitely depend on the inputs but you're right that the width is probably less likely to scale here. Interesting! Thanks for the feedback, maybe I can remove all swearing from my code now.