programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# help calculate growth

john hog
Greenhorn
Posts: 11
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 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
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
the inner loops don't run as many times as the outer loops...

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?