Skip to content

Instantly share code, notes, and snippets.

@mebubo

mebubo/order_of_growth

Created September 8, 2012 12:22
Show Gist options
  • Save mebubo/3674368 to your computer and use it in GitHub Desktop.
Save mebubo/3674368 to your computer and use it in GitHub Desktop.
Download ZIP
Estimate order of growth
Raw
order_of_growth
What is the order of growth of the worst case running time of the following code fragment as a function of N?
int sum = 0;
for (int i = 1; i <= N*N; i = i*2)
for (int j = 0; j < i; j++)
sum++;
The body of the innermost loop executes 1 + 2 + 4 + 8 + ... + N^2 ~ 2 N^2 times.
int sum = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= i*i; j++)
sum++;
The body of the innermost loop executes 1 + 4 + 9 + 16 + ... + N^2 ~ 1/3 N^3 times.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment