How do I calculate the number of times each line of code is executed?

Question

I have some pseudocode where I have to calculate the number of times the code is executed. The code is provided below.

    Historgram1(A,B,N)
    1     for k = 1 to N
    2          B[k] = 0
    3          for i = 1 to N
    4               if A[i] == k
    5               then B[k] = B[k] + 1

I know that line one would run n times but I am not sure about the others. I am also assuming that line 2 would run at least once since we are setting B[k] to a value of zero or would it be n + 1?

I am also unsure how to calculate th subsequent lines. Any help or guidance would be much appreciated.

Answer 1

Obviously, 1 and the whole loop body (2 to 5) are executed N times (for all values of k).

On every iteration of the outer loop, the inner loop (3) is executed N times (for all values of i), as is line 4; but line 5 is executed conditionally, only if A[i]==k.

So far we can say:

• 1, 2: N times
• 3, 4: N² times.

Now line 5 is executed every time some A[i] equals some k in [1, N]. This may occur at most N times (once per A[i]), but might never occur, that's all we can say without knowing more about A.

The global behavior of the algorithm is O(N²), due to lines 3 and 4.

---

Anyway, the function name hints that we are computing an histogram, so it is likely that most of the values are in range [1,k] (unless the choice of the bins is very poor). So we can conjecture that line 5 is executed close to N times, without exceeding it.

This program uses a very poor method to compute the histogram, as this can be done in time O(N).