Does time complexity change when two nested loops are re-written into a single loop?-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.

CodePudding user response：

Let me complement the other answers.

Does time complexity change when two nested loops are re-written into a single loop?

If they do the same work, complexity does not change. :-) If it does, then (at least) one of them is doing unnecessary work.

I apologize if going too far, but let me guess: Your thinking was:

nested loops --> multiply, i.e. "n * n" (or "n * m"), where "n" is "the usual".
single loop --> use "n" as-is, where "n" is "the usual". I am guessing in most exercises you have seen "n" for "size".

If that is your thinking, it just needs one adjustment: for the single loop, if "n" is the length of the loop, note that n = len(a) * len(a); if you change the meaning of "n" from one problem to the other you cannot compare (for the nested loops, n = len(a)). In any case, both codes have O(len(a) * len(a)) complexity, which is what you already found.