La matrice ha 4x4 = 16 elementi. Sia A = { a_0, a_1, ..., a_15} tale matrice.
La rotazione della matrice A in senso orario di un passo genera una nuova matrice A' = (a_i_0, a_i_1, ..., a_i_15} dove x' = (i_0, i_1, ..., i_15} è una permutazione di x = (0, 1, ..., 15) con i_j != j per 0 <= j <= 15. Pertanto l'algoritmo per ruotare la matrice di un passo in senso orario è O(16).

Per me, più veloce di così si muore. Devi spostare 16 elementi e fai 16 operazioni di assegnazione.

Non vedo come si possa velocizzare.
Se qualcuno ha un algoritmo migliore sono tutt'orecchi