Python 3 function to rotate an image 90°

A coding challenge that rotates an image 90 degrees counterclockwise. The image is represented as an array matrix. I believe the time complexity is O(n²), but I’d like to know for sure, as well as any other feedback.

def rotate_image(img):
    rotated_image = [[] for x in range(len(img))]
    for i in range(len(img)):
        for j in range(len(img[i])):
          rotated_image[len(img) - j - 1].append(img[i][j])
    return rotated_image

Example usage:

image = [
  [1, 1, 5, 9, 9],
  [2, 2, 6, 0, 0],
  [3, 3, 7, 1, 1],
  [4, 4, 8, 2, 2],
  [5, 5, 9, 3, 3]
]

rotated_img = rotate_image(image)
for i in rotated_img:
    print(i)

Outputs:

[9, 0, 1, 2, 3]
[9, 0, 1, 2, 3]
[5, 6, 7, 8, 9]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

I believe the time complexity is $O(n^2)$, but I’d like to know for sure

There’s a general method for figuring out the time complexity for a piece of code, which is to annotate each line with the count of times it executes, and the average time it takes to execute, and then multiply and add. Before we do this it helps to rewrite the code so that just one thing is happening on each line.

CODE                                   COUNT   TIME
=====================================  ======  ====
def rotate_image(img):                 
    n = len(img)                       1       t0
    indexes = range(n)                 1       t1
    rotated_image = []                 1       t2
    for _ in indexes:                  n       t3
        rotated_image.append([])       n       t4   (*)
    for i in indexes:                  n       t5
        for j in indexes:              n*n     t6
            k = n - j - 1              n*n     t7
            row = rotated_image[k]     n*n     t8
            entry = img[i][j]          n*n     t9
            row.append(entry)          n*n     t10  (*)
    return rotated_image               1       t11

Here $t_0, t_1, ldots, t_{11}$ are constants giving the average time taken to execute each line of code (their exact values don’t matter for the big-O analysis).

How do I know that these are all constants, and don’t depend on $n$? Well, I used my knowledge about how Python is implemented, but in cases of doubt I consulted the Time Complexity page on the Python Wiki. This tells us, for example, that getting the length of a list takes $O(1)$ (and so $t_0$ is constant); that getting an item from a list takes $O(1)$ (and so $t_8$ and $t_9$ are constant). The two lines marked (*) have calls to list.append: the Time Complexity page tells us that these calls take amortized time $O(1)$. This means that the time taken by individual calls may vary, but on average it is constant.

So, adding all this up, the total time taken on input of size $n×n$ is