Page 1 of 1

Determining run-time complexity

Posted: Sun Sep 06, 2009 12:44 pm
by superdezign
This is fairly basic, but something that I am mathematically stuck on for my homework (yes, homework).

For the psuedocode:

Code: Select all

for(int i = 0; i < n; i++)
    for(int j = i; j <= n; j++)
        for(int k = i; k <= j; k++)
            sum++;
I am supposed to determine the how many times the last statement (line 4) is executed. n is an arbitrary variable that I must solve my answer in terms of. I'll explain my logic and, hopefully, someone can find my flaw or lead me in the right direction.

Line 4 executes only when k <= j. k ranges from i to j, inclusive. j ranges from i to n, inclusive. i ranges from 0 to n-1, inclusive.

Let's follow the process to find the pattern, starting with i = 0:
When i = 0, j ranges from 0 to n. k ranges from 0 to j.
Line 4 is called 1 time in loop 1, 2 times in loop 2, 3 times in loop 3, … up to n+1 times in the last loop.
When i = 1, j ranges from 1 to n. k ranges from 1 to j.
Line 4 is called 1 time in loop 1, 2 times in loop 2, 3 times in loop 3, … up to n times in the last loop.


This continues until i = n-1. The range of k decrements by 1 in each iteration of the loop on line 2. So, line 3 is executed 1 less time for each iteration of the loop on line 2. Since i does not range all the way to n, j and k will never start at n, meaning that that there will never be a time when lines 3 & 4 are only executed once in a loop. My equation at this point for the number of times that line 4 is run is as follows:

Code: Select all

T[size=70]4[/size] = (1+2+3+ … +(n-1)+n+(n+1)) + (1+2+3+ … +(n-1)+n) + (1+2+3+ … +(n-1)) + … + (1+2+3) + (1+2)
My assumption is that there are n terms in this equation. I am fairly certain that this is accurate, but where to go from this point is beyond me. I have tried two approaches:
  • factoring the terms by iterations, and
  • factoring the terms by common terms.
For the first approach, I just simplified the adding of consecutive integers into ½n(n+1) form:

Code: Select all

T[size=70]4[/size] = ½(n+1)(n+2) + ½n(n+1) + ½(n-1)(n) + … + ½(3)(4) + ½(2)(3)
T[size=70]4[/size] = ½[(n+2)(n+1) + (n+1)(n) + (n)(n-1) + … + (4)(3) + (3)(2)]
However, I'm not sure how to simplify it any further than that. If anyone knows of a technique, I'd appreciate it.

The other approach was to group like terms (i.e. (n+1), n, (n-1), etc):

Code: Select all

T[size=70]4[/size] = (n-1)(1) + (n-1)(2) + (n-2)(3) + (n-3)(4) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n) + 1(n+1)
T[size=70]4[/size] = 1(n-1) + 2(n-1) + 3(n-2) + 4(n-3) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n) + (n+1)
T[size=70]4[/size] = [1(n) + 2(n-1) + 3(n-2) + 4(n-3) + … + 5(n-3) + 4(n-2) + 3(n-1) + 2(n)] + (n+1) - 1
T[size=70]4[/size] = [(n+1) + 3(n) + 5(n-1) + 7(n-2) + 9(n-3) + …] - 1
But, again, I have no idea where to go from here.


Any help would be appreciated. ^^

Re: Determining run-time complexity

Posted: Mon Sep 07, 2009 12:29 am
by Eric!
Have you tried a few numbers to make sure your formula works?
superdezign wrote:

Code: Select all

T[size=70]4[/size] = (1+2+3+ … +(n-1)+n+(n+1)) + (1+2+3+ … +(n-1)+n) + (1+2+3+ … +(n-1)) + … + (1+2+3) + (1+2)
I think summations might be better. I'm using the word SUM in place for the SIGMA symbol
(1+2+3+...+(n-1)+(n+1)) is SUM(n+1)

(1+2+3+ … +(n-1)+n) is SUM(n)

(1+2+3+ … +(n-1)) is SUM(n-1)

then add the constants. You could further simplify

SUM(n+1) + SUM(n)+SUM(n-1)+ 9
to
3*SUM(n) + 9

Anyway that's the math, but I'm not sure your expression is correct...I didn't check it. Run some numbers through it to test it. Now that I look at it, I don't think it is right because the equation says if n=0 line 4 should be run 9 times....

Re: Determining run-time complexity

Posted: Mon Sep 07, 2009 11:30 am
by Eric!
F(x)=Σ(x*(x+1)/2) (as x=0 to x=n)

You can test it here:
http://www.math.sc.edu/cgi-bin/sumcgi/calculator.pl
as and example x=0 to x=10 use "sigma[0,10,k*(k+1)/2]"

Since you didn't try to solve g(x) I didn't really look at it because it is his homework after all. :D

Re: Determining run-time complexity

Posted: Mon Sep 07, 2009 1:16 pm
by Eric!
Oh, I see how you wrote it now. For x=n loops, sum=f(x+1)-1
or

sum=Σ(x*(x+1)/2) - 1 for (x=0 to n+1)

as and example where n=10, x=0 to x=10 use "sigma[0,11,k*(k+1)/2] - 1"
on
http://www.math.sc.edu/cgi-bin/sumcgi/calculator.pl

There isn't a closed form solution for this that I can see. You have to use a series summation to solve it.

Re: Determining run-time complexity

Posted: Mon Sep 07, 2009 6:33 pm
by superdezign
T4(n) = (1+2+...+(n-1)+n+(n+1)) + (1+2+...+(n-1)+n) + (1+2+...+(n-1)) + … + (1+2)
T4(n) = ½(n+1)(n+2) + ½n(n+1) + ½(n-1)(n) + … + ½(3)(4) + ½(2)(3)
T4(n) = ½∑(n+1)(n+2)
T4(n) = ½∑(n²+3n+2)
T4(n) = ½∑n² + (3/2)∑n + ∑1
T4(n) = ½(1/6)n(n+1)(2n+1) + (3/2)½n(n+1) + n
T4(n) = (1/12)n(n+1)(2n+1) + (3/4)n(n+1) + n

Converting to summation notation, then converting back was what I needed to do. Tyvm ~Eric! for the idea.

Re: Determining run-time complexity

Posted: Mon Sep 07, 2009 7:32 pm
by Eric!
Ok, so I have to check this now.
sum=f(x)=Σ(x*(x+1)/2) - 1 (where x=0 to x=n+1)

for x=n+1 transpose the equation
½∑(n+1)*(n+2) - 1
½∑(n²+3n+2) - 1
½∑n² + 3/2∑n + ∑ 1 - 1

(1/12)n(n+1)(2n+1) + (3/4)n(n+1) + n - 1

Now if it weren't for the -1 it would work.... I'll let McInfo figure that one out.

By the way, what are those summation transforms called where
∑n² = 1/6*n*(n+1)*(2n+1)

I searched for those all over the internet but couldn't remember what they were called (it's been 20+ years now)...so I gave up and left it in a summation.

Re: Determining run-time complexity

Posted: Mon Sep 07, 2009 8:04 pm
by Eran
By the way, what are those summation transforms called where
induction furmulas

Re: Determining run-time complexity

Posted: Mon Sep 07, 2009 8:13 pm
by superdezign
Eric! wrote:Now if it weren't for the -1 it would work...
There is no "- 1" in the equation. I'll explain this to confirm my thought process. :P

1+2+3+...+n equals ∑i from i=1 to n, which is equal to ½n(n+1).

So when we factor:

T4(n) = (1+2+...+(n-1)+n+(n+1)) + (1+2+...+(n-1)+n) + (1+2+...+(n-1)) + … + (1+2)

We get:

T4(n) = (∑i from i=1 to n+1) + (∑i from i=1 to n) + (∑i from i=1 to n-1) + … + (∑i from i=1 to 2)
T4(n) = (½(n+1)((n+1)+1)) + (½n(n+1)) + (½(n-1)((n-1)+1)) + … + (½(2)(2+1))
T4(n) = ½(n+1)(n+2) + ½n(n+1) + ½(n-1)(n) + … + ½(2)(3)

When we turn that into a summation, the first term is ½(2)(3) and the last term is ½(n+1)(n+2).

Our summation is ∑½(i+1)(i+2) from i=1 to n.
When i=1, the first term is ½(2)(3).
When i=n, the last term is ½(n+1)(n+2).

Then, we continue the algebra from there.
Eric! wrote:By the way, what are those summation transforms called where
∑n² = 1/6*n*(n+1)*(2n+1)
I dunno. ~pytrin does though. :P

Re: Determining run-time complexity

Posted: Tue Sep 08, 2009 10:28 am
by Eric!
Induction formulas...now I can sleep again.

I think the -1 was a by product of going 0 to n+1 and I didn't transpose McInfos equation right. Because the summation form McInfo did works but you have to increase the index by one. I see what you did with the factoring better now and how I screwed up my attempt in the first post.