Hey guys I am currently taking Data Structures using C, we are just now getting to Growth Analysis.

Everywhere on the web is explaining it in a purely mathematical way, however our homework is covered with a programming version.

I have no idea what I am doing or what it wants.


The question reads as follows:

"Describe it's growth function with detail in terms of 'n'"
"What is it's simplified bounding function?"
"Using the bounding function, how much slower does the algorithm become from 150 to 500,000 elements?"

for (i = 0 to n - 1)
c = i + 1
for (j = c to n)
arr[j] += arr[i]
for (k = c to 0 step -1)
arr[k] *= arr[j]


My work so far:
First loop will run n times
Second loop will run (n * (n/2) + (n/2)) times
Third loop I do not have a function for, I cannot figure it out

I'm assuming its growth function is a function that will give the number of iterations based on given n?
Pretty lost, and I'd be much appreciative of any help and or links

Yes. Also note: your question is improperly formatted, and it only appears as 3 nested loops when I went to reply to your question.

"c = i + 1" is executed exactly n times.

The second loop is executed once for each value of 'c', and it iterates from 1 to n, then 2 to n, and so on. This means arr[j] += arr[i] is executed "n + (n-1) + ... + 2 + 1" times. There are standard ways to calculate this sum in closed form, as a function of 'n', n*(n+1)/2.

The third loop is executed once for each value of 'j', from k=c to 0 by stepping with -1, so arr[k] *= arr[j] is executed n*(n+1)/2 * (2 + 3 + ... + (n+1)) = n*(n+1)/2 * n(n+1)/2 = n^2 * (n+1)^2 / 4



References:
For computing the sum, look up 'sum of first n integers'.
For the logic, spend time reasoning about this program until you can reproduce the same, in a way that makes sense to you. Alternatively, any introductory algorithm / loop analysis. Ultimately, you need to spend most of your time here. The sums won't get any more complicated than that in your CS course.

This post was edited by just_shotmikew2 on Jul 15 2014 07:45pm

The third loop function as you have it is n^2 * (n+1)^2 / 4

if n = 5
That would leave us with 159 iterations or 225


When done manually, there are only 50 iterations?

This post was edited by GODBAAL on Jul 16 2014 02:25am

You are right, there is a mistake in the counting for the third one. The final expression is n(n+5)(n+1)/6.

This is equivalent to /sum_{i=0}^{n-1} (n-1)\cdot (i+2).

In other words, n*2 + (n-1)*3 + (n-2) * 4 + (n-3) * 5 + (n-4) * 6 + ... + 1 * (n+1)

You can verify directly by running your program and counting the number of times the inner loop operation is executed.