30 ms·
Is the underlying algo not O(1)? Under what pairs of two u10000 numbers would you get different execution time?
by throwawaymaths 3y ago
Is the underlying algo not O(1)? Under what pairs of two u10000 numbers would you get different execution time?
- ForkMeOnTinder 3y agoSure, if you ignore the n in n=10000, multiplication is O(1). But the same is true for e.g. heapsort--all lists of 10000 items take asymptotically the same amount of time to sort. But that's a strained interpretation of complexity, and not very useful.
- throwawaymaths 3y agoA heapsort is designed to take a variable number of items at runtime for given code. The n is fixed at compile time in the multiplication examples and is invariant at comptime (in zig).