4 ms·
> You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)! In general, it is O(N). In th
by BeetleB 6y ago
> You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)!
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.
- X6S1x6Okd1st 6y agoYeah 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.
- Wowfunhappy 6y ago> 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!)