Python Time Complexity of a small programm

Question

I want to understand how to calculate the time complexity of the next algorithm. Basically, it is just a random number generator function that takes one single parameter size then, generates a list of random numbers while the length of the lists is different than the size parameter.

I am using random.randrange and datetime.

I am trying to understand how could I calculate the approx. time it will take to run instead of running it. what would be the actual math with these parameters.

I did some test with inputs: 1, 10, 100, 1000, 10000, 100000. Here are my results in a nice table:

Input	Time
1	0.000016
10	0.000022
100	0.000081
1000	0.000690
10000	0.007082
100000	0.068690
1000000	still going on while I write this

From what I understand the time complexity grows linear with N, but how could I do the math to have an approx time without computing this.

Here's the code:

def randomRegisteredVisits(size):
    randomNumbersList = []
    while (len(randomNumbersList) != size):
        randomNumbersList.append(randrange(0, size))
    return randomNumbersList

start_time = datetime.now()
miTestofRandom = randomRegisteredVisits(1000000)
end_time = datetime.now()
print('Duration: {}'.format(end_time - start_time))

"still going on while I write this" seems surprising given the rest of the table. I would think that it should still be less than a second (it is less than a second on my machine). — John Coleman
– John Coleman, Commented Dec 28, 2022 at 15:54
Are you asking how you can interpolate a straight line through the data points you have measured? Or how you can do Cross-multiplication in the simplest case? — mkrieger1
– mkrieger1, Commented Dec 28, 2022 at 15:56
I tried multiplying 1,000,000 times the amount of time for 100,000 and then dividing it by 100,000 and the result is 6.869 but at least in my computer it won't happen at that time — Joe
– Joe, Commented Dec 28, 2022 at 16:30
Ok, finally had a chance to try it on my computer. It took almost a second to run it for an input of 1,000,000 and 10 secs for it to run on an input of 10,000,000. — Phong Phuong
– Phong Phuong, Commented Dec 29, 2022 at 7:54

Michael M. · Accepted Answer · 2022-12-28 15:48:28Z

3

Time complexity is O(n), so it is linear.

It's linear as there is a single loop that loops for the entire range. If there was a loop inside loop then the time complexity would be O(n*n), or O(n^2)

edited Dec 28, 2022 at 15:48

Michael M.

11.2k11 gold badges22 silver badges46 bronze badges

answered Dec 28, 2022 at 15:43

Phong Phuong

6556 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python Time Complexity of a small programm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related