Quote (xapeu @ Aug 6 2018 09:49am)
I think that bubble sort would not be O(n) in this case.
If you had [1, 2, 3, ..., n] in your array and changed the last element to a small one like [1, 2, 3, ..., n - 1, 0] the complexity would still be O(n^2) since you would need n iterations over the n elements to move the 0 backwards 1 position at a time.
Let me know if i missed something
what if you go forwards then backwards? so 2k passes instead of just k