@treyhunner
I still do struggle with the exact meaning of O(log n) but I actually did not come into a (hobby) situation where it did actually matter. O(1), O(n) or O(n^2) made click pretty fast. In fact they were nifty terse symbols for situations I ran (hit the bottom) into earlier.
OT: A bigger mental impact was the realization that SQL is “just” set-theory. Now sets are everywhere …
@spencer interestingly O(log n) I have intuition about and can explain but O(n log n) I struggle with.
Here's my log n explanation: I'm thinking of a number from 1 to 100. After you try to guess my number I'll tell you either "correct", "lower", or "higher". Your most sensible first guess is 50. Then it's either 25 or 75 (depending on whether I said lower or higher) and so on.
You will always guess correctly within 7 guesses.
If it were 1 to 10,000 you'd guess within about 20.
@treyhunner THIS is a very good explanation with an example algorithm I even used recently. So it's like ceil(log(n, 2)). Roughly said finding a value within a binary tree usually has a complexity of O(log n)!?
When did the practical relevance of time complexity really click for you?
Meaning, when did you realize that this style of "thinking in orders of magnitude" is helpful for avoiding N+1 problems or other unnecessary loops (or something even deeper if you've needed to care/think about n log n, log n, etc.)?
@treyhunner@gkapfham -- hi again trey! (thanks greg for the boost) ... there should be a term when you re-find a colleague on mastodon whom you haven't heard from in years since you quit twitter
@treyhunner counting cycles in assembly really drove that home. It’s one thing to know something is faster but another to see it being the difference between completing shortly and hogging the 4MHz PC for an hour.
Also back then they weren’t blog posts but text files shared on bulletin boards 😁
@treyhunner Maybe a more defensible point is “use really slow computers handed down from your relatives so you can't afford not to think about performance”?
Come to think of it, I want everyone building front-end websites to use their grandfather's old budget Android phone.
@treyhunner It's just algebra, right? I don't know how it would click with anyone who hasn't invested the time to get a feel for how algebra works.
I'm still waiting for a time in my career when big O notation thoughts are useful. Performance problems are rarely related to low level algorithms. What is the big O/time complexity of not realizing you need to turn off culture-aware comparisons to get a 1000x speedup in C# string handling? Or using orjson instead of import json?
@mistersql@treyhunner the one area it’s come up most for me professionally has been using SQL with ORMs: the difference between O(1) vs O(n) is hard to miss when the times are network call level.
(I’m also reminded of a certain architect who designed an SPA to do XHRs in a nested loop and then announced that the network was too slow)
@manlycoffee I don't need help with understanding it. I'm trying to understand what's worked for others.
I learned time complexity in a CS degree where I needed to internalize it to pass the class. For those working in a non-academic setting, I wonder where the typical struggle is.
I'm so far thinking it's in recognizing the real word application. Seeing O(n^2) code that loops short and efficient but implicitly causes a loop-within-a-loop and realizing noting the speedup when moving to O(n).
Add comment