Hopefully this question isn't too simple for this site.
I'm doing a CompSci algorithms course, and trying to understand various growth rates.
A function with cubic complexity such as the 3Sum problem seems to work like this. Every time you double the input size, the running time multiplies by 8. My sample data looks like this:
1024, 50.94
512, 6.33
256, 0.8
128, 0.10
64, 0.01
Obviously this applies to regular math:
3^3 = 27
6^3 = 216
12^3 = 1728
and 27 * 8 = 216, 216 * 8 = 1728.
I've been trying to figure this out so I can understand it, but my Math isn't very great and I'm not sure what to Google, so I'm not having much look.
Why does a cubic function work like this, with running time multiplying by 8 every time the input doubles?
Define $f(x) = x^3$. Then $f(2x) = (2x)^3 = 2^3 x^3 = 8x^3$. The ratio $\dfrac{f(2x)}{f(x)} = \dfrac{8x^3}{x^3} = 8$.