2 ms·
It was the contrary for me. I think it helps understanding that we are actually put a value to each line of code that gets executed, but instead of microbenchma
by kaba0 6y ago
It was the contrary for me. I think it helps understanding that we are actually put a value to each line of code that gets executed, but instead of microbenchmarking, we do it in an abstract way, say print gets c1 constant, addition gets c2 and the like. For loops will multiply the instructions’ sum inside them by the number of times they get executed. And basically that’s it. You sum the whole thing and get something like (c1+c2)n+c3 for a for loop over an n element list or something with two instructions inside and one other outside the loop. Since these were arbitrary constants, c1 and c2 can be replaced by another one, so you’ve got cn+c3, and since (I’m not gonna be mathematically rigorous here) as n changes, it will be much larger than the others, we are only interested in it, hence it was an O(n) algorithm.
The eye-opening thing about it was that for simple algorithms, I only need high-school math to analyze them for different measurements. Like, memory allocation is costly for this sort of application and I want to measure that, just count each malloc instead! (But do note that it is quite hard/impossible to rigorously analyze programs for modern CPUs with cache misses and the like)