posted 10 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