Last active
November 9, 2015 23:16
-
-
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 )?
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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