CODEWITHSUNDEEP
algorithmmathanalysis
generic user007
generic user007

Reputation: 43

Analyze a given program

I am given a segment of code and told to analyze it. I am so confused. I need to figure out how many times foo runs and use that to determine a function of n. I know how many times foo runs, but I am unable to determine the correct function. Here is the code:

j = 1;
while( j <= n/2 )
{
   i = 1;
   while( i <= j )
   {
      foo;
      i++;
   }
   j++;
}

I know that foo runs in a pattern where half of n is added to the runs. So for instance, when n = 2, foo runs 1 time, when n = 4, foo runs 3 times, when n = 6, foo runs 6 times, etc. Something like this:

n = 2   runs -> j = 1 *          1 run


n = 4   runs -> j = 1 * 
                j = 2 * *        3 runs

n = 6   runs -> j = 1 * 
                j = 2 * *
                j = 3 * * *      6 runs

n = 8   runs -> j = 1 *
                j = 2 * *
                j = 3 * * *
                j = 4 * * * *    10 runs

Maybe I am just over thinking this, but I have been staring at my notebook for hours trying to come up with some function in terms of only n that follows this behavior. Can anyone help?

EDIT I have another question. How do I know if this function is in Big-O, or Big-Theta? Is it something to do with using a while loop instead of a for loop?

Upvotes: 2

Views: 70

Answers (2)

Ami Tavory
Ami Tavory

Reputation: 76297

j runs n / 2 times. For each such iteration, i runs j times. For each such iteration of i, foo is called. So the number of calls is

∑j = 1n / 2 [j] = (1 + n / 2) n / 4 = Θ(n2).

It's just an arithmetic series from 1 to n / 2.

Upvotes: 1

Aravind
Aravind

Reputation: 3179

Once we realize that the bulk of the work is done by the inner while loop, we can compute the runtime(for a given n) as the number of times the inner while loop runs:

1+2+3+...n/2

which is by summation formula

= O(n2).

Upvotes: 1

Related Questions