• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

help calculate growth

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
the inner loops don't run as many times as the outer loops...
 
reply
    Bookmark Topic Watch Topic
  • New Topic