I am working with a sort like a bubble sort but the difference is that it works both ways from left to right. Like, consider an array: 27 9 43 12 5 After going from left to right: 9 27 12 5 43 (43 is in the right position) After going from right to left: 5 9 27 12 43 (5 is in the right position) and it goes on. Now, I have to prove the worst-case time complexity is O(n^2) and also Omega(n^2) and then conclude that it's Theta(n^2) from the previous 2 conclusions.
What I have done is I am trying to conclude that O(n^2) but I can't seem to prove Omega(n^2).