The current solution I'm using involved a transpose and flip. The space complexity is O(1), and the runtime complexity is O(n^2).

I feel this actually runs as a linear runtime, but when I say what the big-Oh is, it sounds quadratic. We could have represented the matrix in a 1-D array with n items, representing a matrix of size sqrt(n). Then the runtime would have been O(n), linear.

Can someone help me understand how to correctly detail the runtime of a matrix?