# Why is this N^3?

Hello,
I had a question on “Space Complexity Mission” on Pg. 1. URL:Learn data science with Python and R projects.

I don’t understand how the space complexity is being calculated.

Here is the code with my code comments (in caps so they stick out)

``````def make_table2(N):
table = [] #DOES THIS COUNT AS N?
for _ in range(N):
row = [] #DOES THIS COUNT AS N?
for _ in range(N):
row.append([1 for _ in range(N)]) #I HAVE NO IDEA ABUT THIS. I THOUGHT IT WOULD BE 1 BECAUSE WE ARE USING ONLY ONE NUMBER. IS THIS THE NESTED LIST?
table.append(row)
return table
``````

I thought it would N^2 but it is N^3 and I don’t know how that is calculated.

Runs `N` times.

Runs `N` times

Runs `N` times.

While the `row.append()` operation will be a constant, the list comprehension is still linear depending on `N`.

The above can be re-written as -

``````for _ in range(N):
row_2 = []
for _ in range(N):
row_2.append(1)
row.append(row_2)
``````

That’s still 3 nested for loops.

Note While you can re-write the list comprehension into the above for loop, the list comprehension is still a bit faster than the for loop equivalent. I am just expanding it to help you better understand the breakdown.

1 Like

Hi @the_doctor,
Thank you for breaking this out (or down?) it helped a lot. I can see where we get N^3 now. Just another question. I wasn’t focusing on the for-loops originally. I was focusing on the variables that were assigned the empty lists (i.e., table and row) for N. Should I not be doing that in the future for space complexity?

I am really sorry!!

I misread the question here and didn’t pay enough attention. My response was based on time complexity and not on space.

I will go through it again and answer it accordingly once I make better sense of the content around this as well.

OK, No worries @the_doctor. You know more than me ! I actually LOVE time complexity ; space complexity…not so much Hey!

So, yes. It’s still N^3 because there are three lists in the function that grow in size depending on `N` -

• `[1 for _ in range(N)]`
• `row`
• `table`
1 Like