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 - 
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 -
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 -
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!
