0
$\begingroup$

This is the algorithm I was trying to find the runtime of (doSomething) -

Procedure findMinMax(int A[], int start, int end)
int min = max = A[start]
int i = j = start
for(int k = start; k <= end; k++)
if(A[k] < min)
i = k
min = A[k]
if(A[k] > max)
j = k
max = A[k]

end for
return {i, j}
end findMinMax

Procedure swap(int A[], int i, int j)
int temp = A[i]
A[i] = A[j]
A[j] = temp
end swap

Algorithm doSomething(A[])
Input: array A of N integers
Output: ?
int i = 0
int j = N-1
while(j - i > 0)
int[] minMax = findMinMax(A, i, j)
int min = minMax[0]
int max = minMax[1]
if(min == j && max == i)
swap(A, min, max)
else if(min == j)
swap(A, i, min)
swap(A, j, max)
else if(max == i)
swap(A, j, max)
swap(A, i, min)
else
swap(A, i, min)
swap(A, j, max)
i++
j--
end while
return A
end doSomething

The indenting of the code is bad in the code block, so here is an image of the code with proper indenting if that helps - enter image description here

The while loop runs n/2 times. This is because i is always incremented by 1 at the end of the while loop and j is always decremented by 1. None of the helper methods called inside of the while loop and none of the other constant time statements called changes i and j, so the while loop ALWAYS runs n/2 times.

Inside of the while loop, the swap functions are called. These are of O(1) constant time and don't affect the runtime. But, findMinMax is also called, which has an O(N) runtime.

In my eyes, I thought that the overall runtime of doSomething would be O(NlogN). The while loop running n/2 times would be equivalent to something like: "for(int i = 0; i < N; i += 2)". That for loop by itself (not considering what is inside of it) has a runtime of O(logN). I figured the same logic applies here and that the while loop has a runtime of O(logN). Multiply that by the runtime of findMinMax which is inside of the while loop body and you get O(NlogN).

However, the answer key disagrees. The answer key states that the runtime of the algorithm is O(N^2).

The reasoning is -

enter image description here

That doesn't really make sense to me. Why was a summation used? I thought they were only used to find runtimes when there was an inner loop dependent on the outer loop. Furthermore, why does 2k or 2k + 1 go inside of the summation?

I also tried using a summation for something like -

for(int i = 0; i < N; i+=2) {
   //O(1) operation
}

I got the summation - enter image description here

which simplifies to N/2, and thus O(N), since the 1/2 constant gets factored out.

I obviously do not see why a summation was used for the doSomething algorithm runtime calculation, especially since there was no inner loop which depended on the outer loop (i.e. "for(j = i + 1)"). The summation logic didn't even work for that other code block I posted just above.

Any help/clarifications would be appreciated!

$\endgroup$
2
  • $\begingroup$ Please do not use edits to remove your posts. Instead, you can (soft)-delete your question. $\endgroup$ – Discrete lizard Apr 8 '20 at 12:22
  • $\begingroup$ Do not redact your posts and delete content. $\endgroup$ – 6005 Apr 8 '20 at 12:22
1
$\begingroup$

I figured out why the runtime is O(N^2).

Yes, the while loop does run N/2 times. However, that is equivalent to -

"for(int i = 0; i < N; i+=2)" which has a runtime of O(N) still.

I confused it with -

"for(int i = 0; i < N; i *= 2)" which has a runtime of O(logN).

The summation also results in the correct answer in this instance.

$\endgroup$
1
$\begingroup$

The OP has already understood the solution, but still:

findMinMax procedure given above is just finding the maximum and minimum element in the array. It has a runtime of O(N).

swap procedure just swaps two array elements given by their indices, which is O(1).

doSomething is an interesting procedure. It seems to be some kind of a variant of selection sort, where minimum element is always swapped with i and maximum element is swapped with j.

The while loop in doSomething runs a total of N/2 times. (i goes from 0 to N/2 and j goes from N-1 to N/2.)

The total time complexity will be (number of times the while loop is run) * (runtime of each while loop).

However, here, the time complexity of findMinMax is not always N. It is O(end-start). Hence, if we just multiply the runtimes, we will get an upper bound, but not necessarily a tight upper bound.

To get the tight upper bound on the runtime, we need to find this sum: (Assuming N is even) $$ \begin{align} \sum_{start=0, end=N-1, start<end}^{} (end-start) & = N + N-2 + N-4 + ... + 4 + 2 \\ & = 2 * (N/2 + (N/2 -1) + (N/2 -2) + ... + 2 + 1) \\ & = 2 * \frac{(N/2)*(N/2 + 1)}{2} \\ & = O(N^2) \end{align} $$

To OP: No, one does not need an inner loop dependent on an outer loop to sum their runtimes. Just having a nested loop means the total time will be (the number of times the outer loop runs) * (the number of times the inner loop runs) * (complexity of the inner loop). Anyway, it's better to find complexity through the basic concepts and avoid such shortcut rules.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.