What is the execution time T(n) of the algorithms? [closed]

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situ开发者_开发百科ation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. Closed 10 years ago.

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)

Algorithm 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

Algorithm 2:

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?

---

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.

---

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.