Anyone good with algorithms?

[corby]

Hey guys/gals i need some help with finding the T(n) complexity of the following for nested loops

sum = 0
for i = 0 to n-1 do
[INDENT]for j = 0 to (i^2) - 1 do[/INDENT]
[INDENT][INDENT]for k = 0 to j - 1[/INDENT][/INDENT]
[INDENT][INDENT][INDENT]sum = sum + 1[/INDENT][/INDENT][/INDENT]
[INDENT][INDENT]end-for[/INDENT][/INDENT]
[INDENT]end-for[/INDENT]
end-for
write sum

I am confused as to how to analyze this. Any suggestion? I do know that you start with innermost loop but what do i do upper bound minus lower bound plus 1?

[mrnutty]

>>for i = 0 to n-1 do

how long does this loop run for?

>>for j = 0 to (i^2) - 1 do

Realize that this loop runs for (i^2)-1, for EACH i in the loop before this

>>for k = 0 to j - 1

Realize that this loop runs for j times, for EACH j.

[Rashakil Fol]

Just compute the following integral.

[tex]\int_0^n \int_0^{i^2} \int_0^j 1 dk dj di[/tex]

[Rashakil Fol]

Just compute the following integral.

[tex]\int_0^n \int_0^{i^2} \int_0^j 1 dk dj di[/tex]

And here's how you do it.

[tex]\int_0^n \int_0^{i^2} \int_0^j 1 dk dj di = \int_0^n \int_0^{i^2} j dj di = \int_0^n \frac{i^4}{2} di = \frac{n^5}{10} [/tex]

But that's kind of not relevant. The point of expressing the sum in terms of integrals is not that it gives you an exact number of instructions -- it's that the big O expressions of an integral on an interval are going to be the same as those of the Reimann sum.

[tex]\int_0^n \int_0^{i^2} \int_0^j 1 dk dj di \in \int_0^n \int_0^{i^2} \int_0^j O(1) dk dj di = \int_0^n \int_0^{i^2} O(j) dj di = \int_0^n O(i^4) di = O(n^5)[/tex]

[corby]

And here's how you do it.

[tex]\int_0^n \int_0^{i^2} \int_0^j 1 dk dj di = \int_0^n \int_0^{i^2} j dj di = \int_0^n \frac{i^4}{2} di = \frac{n^5}{10} [/tex]

But that's kind of not relevant. The point of expressing the sum in terms of integrals is not that it gives you an exact number of instructions -- it's that the big O expressions of an integral on an interval are going to be the same as those of the Reimann sum.

[tex]\int_0^n \int_0^{i^2} \int_0^j 1 dk dj di \in \int_0^n \int_0^{i^2} \int_0^j O(1) dk dj di = \int_0^n \int_0^{i^2} O(j) dj di = \int_0^n O(i^4) di = O(n^5)[/tex]

tnx bro