Big O Complexity Python, find out running time for input of size 'n'

The number of times the while loop runs is linearly related to the size of n, and in each of these iterations, [i]*n creates a list and adds i to it n times, which is another iteration. One iteration nested inside another is O(n^2) time complexity.

None of the given options is correct. Let's rewrite the function ever so slightly: we're only going to rename the parameter from n to x:

def 2d_list(x):
    i = 0
    data = []
    while i < x:            
        data.append([i] * x)
        i += 1
    return data

Now how many operations do we have? There are still O(x^2) operations: For each of the x values of i, we have to create a list with x elements.

But what's the input size n? That's the number of bits you need to represent the number x. The number x grows much faster than n: you can basically double the size of x without adding more than 1 bit to the input.

As a result, you have n = log x, or x = 2**n. This means the time complexity of your function is actually O(4**n).