Re:Big O, Little N
by Wowfunhappy on Friday October 02, 2020 @04:15PM
(#24666597)
> When your N is fixed (or even upper bounded), then it is always O(1).
I had to read this sentence over several times. I... think you've just filled in a missing piece of my college CompSci education.
Previously, I never really understand why we measured algorithms this way, beyond "it's a rough classification and nothing is perfect." What I didn't quite realize until just now is, this classification assumes N is a variable that could be any value in the universe—and so you have to optimize for that eventuality.
If N is known, the iterations don't matter—because of course they don't.
(Disclaimer: I've been out of college for a while and I don't use algorithms in my daily life, it's possible I just forgot this. Or that I'm making a fool of myself right now!)
Re:Big O, Little N
by X6S1x6Okd1st on Friday October 02, 2020 @04:05PM
(#24666528)
Yeah I was working on an elevator control problem and made mention about how this doesn't have great time complexity, but the number of floors is surely less than 163.
In general, it is O(N). In this example, it is O(1). When your N is fixed (or even upper bounded), then it is always O(1). This is standard in how it is taught, and I've even said O(1) in interviews where I had a nested for loop, because the size of the iteration was fixed in both loops. The interviewer agreed with me.
Heck, I did this even in an interview where N could be arbitrarily large, but I argued that for the problem domain, it is extremely unlikely that N would be bigger than some amount - here N represented the number of direct reports a manager has. I said that in theory it was O(N), but in practice (or on average), it would be O(1). Again, the interviewer accepted the answer.