Why is this N^3?

Q&A DQ Courses
, ,
#1

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.

#2

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
#3

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?

#4

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.

#5

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

#6

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