Happy new year and peace to you all! Can you please explain to me what is the execution time T(n) of the 2 algorithms? Assuming execution time T(n) = # executions of (a:=a+1)
for i ← 1 to n do
for j ← 1 to i do
for k ← j to i+j do
a ← a + 1
end for
end for
end for
for i ← 1 to m do
for j ← 1 to i^2 do
for k ← 1 to j do
a ← a + 1
end for
end for
end for
Execution time T(n) can be found by counting the number of atomic operations that take place (for example, assigning the value a+1 to a). In this case, computing the number operations is not so difficult because in each of your algorithms you have only a single operation, and the number of times its executed is governed by the fixed bounds of your loop.
Because this is homework (or sounds like it) I'm not going to perform the calculations, but do you understand nested loops well enough to determine how many times the body of each will execute?
For these algorithms, you should try to arrive at an expression for a in terms of n (or m, in algorithm 2). For these algorithms, that expression will be a polynomial. The order of that polynomial is really the O(n) complexity of that algorithm. Now with that hint you should be able to complete the homework.
Here's how you approach these:
For the first, figure out how many times the innermost loop executes as function of i and j. Call this number f(i, j). Then we note that
sum(i = 1 to n) sum(j = 1 to i) f(i, j)
would be the desired answer. Then it's a matter of computing this sum. I'll give you a hint: the answer involves knowing how to sum consecutive squares and consecutive integers. (I am 100% certain that your professor went over this in class.)
For the second, approach it similarly. For this one you will need to know the sum of consecutive fourth powers and, again, the sum of consecutive squares.
I have the answer to both of these; if you want, post a solution and I'll check against mine and provide comments.