I changed O(n²) as if it was O(n), but is it actually O(n²)?-CodePudding

Is the time complexity of nested for, while, and if statements the same? Suppose a is given as an array of length n.

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

The for statement above will be O(n²).

i = 0
while i < len(a) * len(a):
    do_something
    i  = 1

At first glance, the above loop can be thought of as O(n), but in the end I think that it is also O(n²).

Am I right?

CodePudding user response：

Am I right?

Yes!

The double loop:

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

has a time complexity of O(n) * O(n) = O(n²) because each loop runs until n.

The single loop:

i = 0
while i < len(a) * len(a):
    do_something
    i  = 1

has a time complexity of O(n * n) = O(n²), because the loop runs until i = n * n = n².

CodePudding user response：

It is indeed still O(n^2). That is especially clear when you look at the loop which has len(a)*len(a) iterations.

You "flattened" the loops, but didn't change the amount of work, therefore it's just a "stylistic" change and has no impact on complexity.

CodePudding user response：

We need to determine time complexity based on the number of operations being carried out by the constructs IMHO. It wouldn't be correct to generalize and say certain loops have a particular time complexity.

The time complexity of nested for loops generally would be o(n squared) - not always. Some involved nested for loops can also have just O(n) complexity. a single if statement would generally be O(1) since you are only doing basic comparisons. while loop could be anything depending on your exit condition.

while it could be useful to keep generalizations such as these in mind, we should always check the number of operations carried out to determine complexity.