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 $$T(n) = t_0 + t_1 + t_2 + t_{11} + n(t_3 + t_4 + t_5) + n^2(t_6 + t_7 + t_8 + t_9 + t_{10}).$$ Since \$n≥0\$ and allIf \$t_i>0\$\$n≥1\$, $$T(n) < n^2(t_0 + t_1 + t_2 + t_3 + t_4 + t_5 + t_6 + t_7 + t_8 + t_9 + t_{10} + t_{11})$$ and so \$T(n) = O(n^2)\$.
Using the same method, we can get lower bounds too. Since \$n≥0\$ andFor all \$t_i>0\$\$n≥0\$, $$T(n) > n^2(t_6 + t_7 + t_8 + t_9 + t_{10})$$ and so \$T(n) = Ω(n^2)\$. Combining these two results, \$T(n) = Θ(n^2)\$.
How do I know that these are all constants? 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 $$T(n) = t_0 + t_1 + t_2 + t_{11} + n(t_3 + t_4 + t_5) + n^2(t_6 + t_7 + t_8 + t_9 + t_{10}).$$ Since \$n≥0\$ and all \$t_i>0\$, $$T(n) < n^2(t_0 + t_1 + t_2 + t_3 + t_4 + t_5 + t_6 + t_7 + t_8 + t_9 + t_{10} + t_{11})$$ and so \$T(n) = O(n^2)\$.
Using the same method, we can get lower bounds too. Since \$n≥0\$ and all \$t_i>0\$, $$T(n) > n^2(t_6 + t_7 + t_8 + t_9 + t_{10})$$ and so \$T(n) = Ω(n^2)\$. Combining these two results, \$T(n) = Θ(n^2)\$.
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 $$T(n) = t_0 + t_1 + t_2 + t_{11} + n(t_3 + t_4 + t_5) + n^2(t_6 + t_7 + t_8 + t_9 + t_{10}).$$ If \$n≥1\$, $$T(n) < n^2(t_0 + t_1 + t_2 + t_3 + t_4 + t_5 + t_6 + t_7 + t_8 + t_9 + t_{10} + t_{11})$$ and so \$T(n) = O(n^2)\$.
Using the same method, we can get lower bounds too. For all \$n≥0\$, $$T(n) > n^2(t_6 + t_7 + t_8 + t_9 + t_{10})$$ and so \$T(n) = Ω(n^2)\$. Combining these two results, \$T(n) = Θ(n^2)\$.
- 50.1k
- 3
- 130
- 210
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.
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? 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 Time Complexity page on the Python Wiki 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\$ input is $$T(n) = t_0 + t_1 + t_2 + t_{11} + n(t_3 + t_4 + t_5) + n^2(t_6 + t_7 + t_8 + t_9 + t_{10}).$$ Since \$n≥0\$ and all \$t_i>0\$, $$T(n) < n^2(t_0 + t_1 + t_2 + t_3 + t_4 + t_5 + t_6 + t_7 + t_8 + t_9 + t_{10} + t_{11})$$ and so \$T(n) = O(n^2)\$.
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. Before we do this it helps to rewrite the code so that just one thing is happening on each line.
Here \$t_0, t_1, \ldots, t_{11}\$ are constants giving the time taken to execute each line of code (their exact values don't matter for the big-O analysis). The two lines marked (*) have calls to list.append: the Time Complexity page on the Python Wiki 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 \$n×ばつn\$ input is $$T(n) = t_0 + t_1 + t_2 + t_{11} + n(t_3 + t_4 + t_5) + n^2(t_6 + t_7 + t_8 + t_9 + t_{10}).$$ Since \$n≥0\$ and all \$t_i>0\$, $$T(n) < n^2(t_0 + t_1 + t_2 + t_3 + t_4 + t_5 + t_6 + t_7 + t_8 + t_9 + t_{10} + t_{11})$$ and so \$T(n) = O(n^2)\$.
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.
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? 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 $$T(n) = t_0 + t_1 + t_2 + t_{11} + n(t_3 + t_4 + t_5) + n^2(t_6 + t_7 + t_8 + t_9 + t_{10}).$$ Since \$n≥0\$ and all \$t_i>0\$, $$T(n) < n^2(t_0 + t_1 + t_2 + t_3 + t_4 + t_5 + t_6 + t_7 + t_8 + t_9 + t_{10} + t_{11})$$ and so \$T(n) = O(n^2)\$.
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. 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 time taken to execute each line of code (their exact values don't matter for the big-O analysis). The two lines marked (*) have calls to list.append: the Time Complexity page on the Python Wiki 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 \$n×ばつn\$ input is $$T(n) = t_0 + t_1 + t_2 + t_{11} + n(t_3 + t_4 + t_5) + n^2(t_6 + t_7 + t_8 + t_9 + t_{10}).$$ Since \$n≥0\$ and all \$t_i>0\$, $$T(n) < n^2(t_0 + t_1 + t_2 + t_3 + t_4 + t_5 + t_6 + t_7 + t_8 + t_9 + t_{10} + t_{11})$$ and so \$T(n) = O(n^2)\$.
Using the same method, we can get lower bounds too. Since \$n≥0\$ and all \$t_i>0\$, $$T(n) > n^2(t_6 + t_7 + t_8 + t_9 + t_{10})$$ and so \$T(n) = Ω(n^2)\$. Combining these two results, \$T(n) = Θ(n^2)\$.
(Once you get comfortable with using this method, the result in simple cases like this will be obvious, and so you can skip the detail, but it's useful to know that you can produce the detail if needed in more complex cases.)