Skip to content

Instantly share code, notes, and snippets.

@bumble-bee-chuna
Last active November 9, 2015 23:16
Show Gist options
  • Save bumble-bee-chuna/84d0fcd6ae0696bfe70c to your computer and use it in GitHub Desktop.
Save bumble-bee-chuna/84d0fcd6ae0696bfe70c to your computer and use it in GitHub Desktop.
How does the powerlaw ( aN^b ) relate to a log-log run time ( lg(T(N)) = b lg N + c )?
The following data is given for the run time of a program:
https://d2gne97vdumgn3.cloudfront.net/api/file/XF3gUiIRRh2321KcJHbO
And then is graphed in a log-log scale graph and through compressing it for a log-log scale graph,
has a slope of 3.
https://d2gne97vdumgn3.cloudfront.net/api/file/n3GlkRKWSg6V1EyKAzOj
The formula for the line can then be described as:
log(T(N)) = b lg N + c
where b is the slope of the line (in this case '3') and c is the value of y
when the line's the x-axis value is 0.
(To clarify when x = 0, y = -33.2103)
What I don't understand is how the powerlaw relates back to this? In this example I'm given,
they use the power law (aNb) for regression and then somehow get the running time of
1.006 * 10-10 * N^3.
I'm wondering how on earth did they come up with that run time from the formula for T(N)?
This is the entire slide: http://i.imgur.com/biJt5TK.png
Please let me know if I need to provide any clarification.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment