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 &lt;= N &lt;= 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.