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)\$.

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)\$.