4 ms·
> IIRC C has an informal guarantee that no primitive syntax will ever cause the CPU to do more than O(1) work at runtime. How about CPUs that have no, say, div
by xigoi 4y ago
> IIRC C has an informal guarantee that no primitive syntax will ever cause the CPU to do more than O(1) work at runtime.
How about CPUs that have no, say, division instruction, so it has to be emulated with a loop?
- naniwaduni 4y agoFixed-width divisions are O(1), just comparatively expensive (and potentially optimized to run in variable time). Consider that you can do long division on pairs of numerals of, say, up to 20 digits and be Pretty Confident of an upper bound on how long it's going to take you (you know it's not going to take more than 20 rounds), even though it's going to take you longer to do that than it would for you to add them.