3 ms·
> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever? Yes, because there
by saagarjha 6y ago
> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever?
Yes, because there is no "n" involved. For example, this code:
for i in 1...1_000_000 {
print(i)
}
return ["a", "e", "i", "o", "u"].contains(character)
is still O(1), it just has a higher constant factor. The only exception is that you could have psuedo-polynomial algorithms that depend on the value input itself, like
func foo(i: Int) {
for _ in 1...i {
print(i)
}
}