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?

3
Contributors
4
Replies
5
Views
8 Years
Discussion Span
Last Post by corby

>>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.

Just compute the following integral.

$$\int_0^n \int_0^{i^2} \int_0^j 1 dk dj di$$

Cool

Just compute the following integral.

$$\int_0^n \int_0^{i^2} \int_0^j 1 dk dj di$$

And here's how you do it.

$$\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}$$

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.

$$\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)$$

And here's how you do it.

$$\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}$$

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.

$$\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)$$

tnx bro

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.