• Post Reply Bookmark Topic Watch Topic
  • New Topic

help calculate growth  RSS feed

 
john hog
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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*i <= N; i = i + 2)
sum++;

the answer is n^1/2 but how?

I am taking an algorithm class and after 2 weeks I still have trouble understanding this stuff. I only understand the basic 1/N/LogN/N^2... but not exactly sure how to break it down line by line to calculate it on my own. It is not sensible to just memorize all the running times so I need to be able to calculate it on the fly. I have reviewed a bit on basic math but I don't know how to break these algorithms down. Here are some others I am confused on.,.

int sum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
for (int k = 0; k < j; k++)
sum++;
The answer is : N^3
The body of the innermost loop executes N choose 3 ~ 1/6 N^3 times.

I get this is N^3 because there are 3 loops but how did it get 1/6 ?


also on calculating growth for sorting I came across this:

insertion sort "if random ordered array uses ~1/4N^2 compares and ~1/4N^2 exchanges"

I understand n^2 but where does 1/4 come out of? It has 2 loops which run N * N times, and thats all I know so far.

thanks
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Go through the loop and count how many times it runs for different values of n. By the way: it should usually be lower case.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the inner loops don't run as many times as the outer loops...
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!