Rotating an NxN matrix

I came up with the following solution for rotating an NxN matrix 90 degrees clockwise, to solve this CodeEval challenge:

Input


The first argument is a file that contains 2D N×N matrices (where 1 <= N <= 10), presented in a serialized form (starting from the upper-left element), one matrix per line. The elements of a matrix are separated by spaces.


For example:

a b c d e f g h i j k l m n o p

Output


Print to stdout matrices rotated 90° clockwise in a serialized form (same as in the input sample).


For example:

m i e a n j f b o k g c p l h d

It looks elegant to me, but can someone explain how its performance compares to the more common solutions mentioned here? Does it have \$O(n^2)\$ time complexity?

import sys, math

for line in open(sys.argv[1]):
    original = line.rstrip().replace(' ', '')
    nSquared = len(original)
    n = int(math.sqrt(nSquared))
    output = ''

    for i in range(nSquared):
        index = n * (n - 1 - i % n) + int(i / n)
        output += original[index] + ' '

    print(output.rstrip())

The expression n * (n - 1 - i % n) + int(i / n) is something I found while observing common patterns among rotated matrices.

-
The formula is elegant, and the approach is correct.

-
You have to be careful with complexities though. Specifically you have to be very clear about what \$n\$ is. Typically complexity is a function of the size of input (which is, provided that \$n\$ is a matrix dimension, \$n^2\$ itself), so I'd qualify your solution as linear. And since each element should be accounted for, no better solution is possible.

-
The asymptotic constant could be better. The problem doesn't ask to rotate the matrix; it is only asks to print the matrix as if it was rotated. In other words, building output is technically a waste of time. Use your formula to print elements as you enumerate them.

StackExchange Code Review Q#82638, answer score: 4