john hog

Greenhorn

Posts: 11

posted 3 years ago

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

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

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