educative.io

How to obtain 32 number of instructions executed?

Courses
,
#1

The question has been updated on 19/01/2020

n1 = outer loop
n2 = inner loop
Inner loop execution only = 1

= [Outer Loop] 2 ∗ (n + 1) + 2(n)
  [Inner Loop] (n * 2)
= 2 * (5 + 1) + 2(5) + (5 * 2)
= 2 * 6 + 10 + 10
= 12 + 10 + 10
= 32

I am wondering how to get 22 for the outer loop.

I can only get a maximum of 12 for the outer loop.
Am I counting it wrongly?

    for (int i = 1; i < input.length; i++) { // 2 costs * 4
            int key = input[i]; // 1 cost * 4
            ...
        }

And the explanation said that the “The inner loop will never run any iterations”, really?
image

Would you please explain how to get 32 for this question?

#2

Might be a slightly late reply but here is how I got 22 for the outer loop:

for (int i = 0; i < input.length; i++) { // consider three parts separately, see below
      int key = input[i]; // (5 runs)
      j = i - 1; // (5 runs)
      /* ignore inner loop */
}
/* the for loop is broken down into three separate parts */
int i = 0; // (1 run) it's executed just at the start of the for loop
i < input.length; // (6 runs) it's executed at the start and again at every iteration
i++; // (5 runs) it's executed at every iteration

Therefore the total for the outer loop is: 5 + 5 + 1 + 6 + 5 = 22
Hope this helps.

I actually don’t think this question is very clear because you don’t really know what to count as a single instruction. For example do you count the “jump” of the for loop itself as an instruction, do you count the “and” operator as an instruction, and do you assume short-circuit evaluation of the “and” operation.