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(n2), 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
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)
[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(n2), 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 t0,t1,…,t11 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 t0 is constant); that getting an item from a list takes O(1) (and so t8 and t9 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