Runtime complexity for Problem 6.23 in v. 1.4.9 (2D Array Rotation)

#1

The 2D array rotation solution says that the run-time complexity for the naive approach is O(n). However, the size of the 2D array is n x n. Shouldn’t the run-time complexity be O(n^2) since we move every element in the original matrix?

Furthermore, it says that the run-time complexity for the recursive approach is O(n lg n). However, I think the recurrence should be T(n) = 4T(n/2) + O(n^2), which reduces to O(n^2 lg n) according to case 2 of the Master Theorem. (I say O(n^2) instead of O(n) because we copy each matrix element to the next quadrant.)

0 Likes
#2

Hey John,

We define N = n^2 = 2^(2k). So the complexity is O(N) instead of O(n). N is a handy notation for writing. Sorry that it may confuse you due to this notation usage.

0 Likes
#3

Ah, now I feel stupid. I skipped over that part of the explanation! Thanks for clarifying.

0 Likes