CODEWITHSUNDEEP
pythonpython-3.xruntimetime-complexity
Jeb
Jeb

Reputation: 170

What is the difference in time complexity between these two blocks of code (if any) and why?

Trying to solidify my knowledge about Time Complexity. I think I know the answer to this, but would like to hear some good explanations.

main = []
while len(main) < 5:
    sub = []
    while len(sub) < 5:
        sub.append(random.randint(1,10))
    main.append(sub)

VS

main = []
sub = []
while len(main) < 5:
    sub.append(random.randint(1,10))
    if len(sub) == 5:
        main.append(list(sub))
        sub = []

Upvotes: 2

Views: 64

Answers (2)

Ken4scholars
Ken4scholars

Reputation: 6296

The time complexity in both are O(1) - constant time because they both perform a constant number of operations as @Yakov Dan already stated.

This is because time complexity is usually expressed as a function of a variable number(say n) and tends to show how changing the value of n will change the time the algorithm will take.

Now, assuming you had n instead of 5, then you would have O(n^2) for both cases. It may be tricky for the second case since a basic way of checking the polynomial complexity is to count the number of nested loops and you can be lead to conclude that the second version is O(n) since it has a single loop.

However, carefully looking at it will show you that the loop runs n(5 in this case) times for sub for each value appended to main, so it is essentially the same.

This of course assumes that the in-built list.append is atomic or runs in a constant time.

Upvotes: 1

Yakov Dan
Yakov Dan

Reputation: 3347

There's no difference, since the time complexity is constant in both cases - you perform a constant amount of operations both times.

Upvotes: 3

Related Questions