What statement is true for this piece of code?

Question

I am preparing myself for my exam, and I am doing some exerices for that - where I came up to a question, I am a little unsure about.

Question:

I am sure about that the answer can't be C or D because the best running time for the code is O(1) and the worst-case running time is O(n).

I also think B must be the right answer as the if-statement inside the forloop compares if A[i] == 0. Which the worst case is N.

What I am unsure about is, when do you call something "array access" and when it is a comparision? That is why I am unsure about, if the answer is B or A.

Answer 1

The answer is B - in the worst case this code makes a total of 2N comparisons. Suppose the loop was empty. It takes N comparisons (i < n) just to run the empty loop. Now consider the if statement inside the loop - that is another N comparisons for a total of 2N comparisons in the worst case.

The answer cannot be C, because in the "best case" we discover that the first element of the array is 0 and the loop returns after making only 2 comparisons, making the best case O(1) constant.

The answer is obviously not D; there is nothing quadratic about this loop. Its obviously linear.

The answer cannot be A, because in the worst case we access the array only N times. This occurs at s[i], just prior to the comparison against 0.

Consider the following equivalent code:

int n = s.length();
for (int i=0; i < n; i++)
{
    int v = s[i];
    if (v == 0)
        return i;
}

Now it should be a little more obvious what counts as a comparison and what counts as an array access. In the worst case we'll access the array N times.

Answer 2

To me it looks like you're right.

• Comparisons: Any use of the operators ==, !=, >, <, >=, <=, custom comparison operators or comparison methods.
• Array accesses: Any arr[i], e.g. arr[i] = x, print(arr[i]) or custom accessors, etc.

So just count them up for the best and worst cases.

• What's the worst case? The worst case is when none of the array elements are zero.
• What's the best case? If the first element is zero (we don't count N being zero, because we want to look at totality of the behaviour as N increases).

How many iterations would it have in those cases? How many array accesses and comparisons? Don't forget the comparison ops in the for-loop itself.

Is the algorithm linear or quadratic in the best and worse cases?