- #1
zorro
- 1,384
- 0
Can someone explain why the running time of following piece of pseudo code is O(n) and not O(n2)?
for i := 0 to n - 1
while A[A] != A
swap(A, A[A])
end while
end for
The for loop executes at most n times and the inner while loop executes at most n-1 times, giving a worst case time of O(n2)
for i := 0 to n - 1
while A[A] != A
swap(A, A[A])
end while
end for
The for loop executes at most n times and the inner while loop executes at most n-1 times, giving a worst case time of O(n2)