Python algorithm complexity with two loops

Asked

Viewed 409 times

6

This algorithm is used to return the element that repeats most in a list:

def algorithm_x(a):
    x = 0
    y = 0
    for i in range(0, len(a)):
        k = 1
        for j in range(i+1, len(a)):
            if a[i] == a[j]:
                k = k + 1
        if x < k:
            x = k
            y = a[i]
    return y

I don’t understand why his complexity is considered O(nˆ2) instead of O(nˆ3), since in the for external you will go through n times, on the inside will go through n*n times. Multiplying the two loops would give n*n*n. Where am I going wrong?

python

2 answers

7


The intern will not travel in n * n, nowhere shows it and it’s an inference from you that does it. Since that information doesn’t exist in the code, you should tell us why you found it.

If it has only one inner bond it has no way of being polynomial in itself. Unless some internal function in it was actually a loop even without you knowing it, but that’s not the case, all functions (and operators) executed in there have complexity O(1).

Even to say it is O(n 2) is also wrong. The approximate correct formula would be O(n*(n/2)) since at each step he will start going through the elements further until at the end he starts at the last element, at the average he performs half of the elements.

The outer loop goes from 0 to the size of the past collection. That’s easy. Let’s say the collection has 6 elements, so the track goes up to 5, it is exclusive.

The internal loop will first start at 1 and go up to 5. In the second step of the external the value of i is 1, then the next internal loop will start from 2 and go up to 5. The next loop will go from 3 to 5, and so it continues until it goes from 5 to 5. So the first loop ran through 5 elements, then 4, then 3, then 2, and finally 1. All adds up to 15, and to calculate the average we divided by the amount of interactions (which were 5), which gives 3, and which is half of 6.

I gave a answer that shows this in more detail and an example. There it becomes clearer the demystification that the amount of loops used always determines the complexity. In some cases yes, so does not serve as a model, serves as an initial indication to be investigated further. In the comments of the other answer I show how what seems to be a complexity can be another if it is deeper, and coincidences cannot be used to demonstrate the real complexity.

  • Thanks for the answer, I still can not understand, because in the internal loop it would travel on average half of the elements, what would be the worst input for this code? perhaps an example will help me to understand.

  • @Pirategull I edited to explain this part.

  • 2

    O(n^2) is equivalent to O(n*(n/2)). Recalling asymptote. So, yes, you could say that the algorithm presented runs on quadratic order and that will be correct. It can also be said that rotate in quadratic function, since any polynomial of degree 2 is a quadratic (including constant and linear factor).

  • 2

    I must also remember here that the Big-O notation is a set, not a specific polynomial. Therefore, to say that n^2 == O(n^2) is a common abuse of writing, when the correct would be to use n^2 ∈ O(n^2). As the set described by O(n**2) is exactly the same as the set defined by O(n*(n/2)), we can write without problems that O(n^2) == O(n*(n/2))

  • @Jeffersonquesado is not, nor does it make sense, are completely different values. You can take any value of `n, let’s take 6, the first formula gives 36 and the second formula gives 18. You can say that O((n 2)/2) == O(n*(n/2)). I’m not really familiar with the theories of that, I know how to calculate what matters as an engineer, and it matters how many steps you take, and that’s how you calculate it. If the theory says that O(n 2) == O(n*(n/2)), then it serves me nothing, but I doubt the theory says so.

  • 1

    So you urgently need to revise your theory. When it comes to asymptotic notation, Quick Sort is O(n^2), but that’s not why you won’t use it for guaranteed random cases where it has behavior O(n log n). It is also worth noting that the function within the large O must be taken into account for when the variable tends to infinity, so replacing by 6 is simply wrong. Remember that asymptotic behavior has nothing to do with how many computations will actually be made, it is a asymptote.

  • 1

    And yes, asymptotic behavior serves to show how fast computational processing time will grow, not to say there will be 18 comparisons. Note that if you fold the n (i.e., take 12 as input), both calculations will be a multiplication by 4: 12*12 = (6*2) * (6*2) = 6*6 * 4 and 12*12/2 = 6*2 * 6*2/2 = 6*(6/2) * 4

  • If it’s true I don’t want to revise the theory, I want to kick it far away, because it doesn’t fit. I just want to know how many steps (proportionally and not in absolute values, of course) something is executed, because it will make all the difference in the final result), anything that gives me a number that does not indicate it clearly does not suit me. Theoretical results don’t give me the sense I need to make decisions. It may be wrong to use Big O for this, it may be, tell me what to use then for what I want that is what matters in fact.

  • 1

    You could say that n**2/2 + n/2 gets closer the behavior that n**2. Using Big-O notation for this is abuse (but how to say that n**2 == O(n**2) is also abuse and everyone does). Of all sorts, in more complex algorithms, very common to use that it has behavior according to O(F(n)) if n <= M and O(G(n)) if M < n. This is done when, for that range of specific values, the accompanying constant F or G makes the function somehow despicable.

  • 1

    It is in this line of reasoning that it is said that the insertion sort has behavior linear for small intervals. And on top of that fact the Tim sort achieves an absolute time optimization in relation to its base algorithm, the merge sort. And it is taking into account the multiplicative factors that normally the quick sort rotate much faster than the merge sort; but there will always be that case where selection sort would give similar performance

  • If you ask me if learning algorithm complexity is useful and many people say they never needed it. I always say I’ve used it my whole life. I may have used it wrong, I may have used the term improperly, but what you’re talking about was never helpful to me, and I’ve never actually used, I’ve used what I always explain. And everybody gets it. I always knew how to choose the proper structures and algorithms doing the math the way I always do because they give me the result that matters, and apparently more accurately :)

  • 1

    Usually when talking about algorithm complexity, we are talking about the "big O" that removes any constants. O(n*(n/2)) = (0.5 n 2) = O(n 2). There are cases where one is interested in the exact number of steps the algorithm will take, but usually not. If to say the exact or average number of steps, the function is simply n*n/2, there is no reason to put O() in the middle.

Show 7 more comments

-1

When we don’t understand a concept, it’s interesting to make a model:

n = 3
for a in range(0, n):
        for b in range(0, n):
                print ("a", a, "b", b)

The output of this program is:

a 0 b 0
a 0 b 1
a 0 b 2
a 1 b 0
a 1 b 1
a 1 b 2
a 2 b 0
a 2 b 1
a 2 b 2

It is clear that the "complexity" was O(n 2), printed 9 lines (3 times 3).

  • 2

    Not a good one. The https://ideone.com/pnYqb5 code is not O(n 2), there is coincidence of some specific case where m and n are equal to be able to say that it is n 2, but it is conceptually wrong and to observe this model thus gives an incorrect idea of what is algorithm complexity. The code https://ideone.com/GMgVx7 is O(n) and does the same thing, the observed result does not indicate what the complexity is.

  • Okay, but the question was whether two nested loops produced a complexity O(n 2) or O(n 3), that was the question. And in my vision you just "unrolled' (unrolled) my routine. You could do something similar with a Bubble Sort, "hiding" complexity by squaring "n" and using a single loop, which doesn’t make it O(n).

  • 3

    His answer tells the person to create a model that gives a false idea. Algorithm complexity is this, not always the visible complexity is the one that actually occurs. The problem is not the question, it is the answer that requires doing something that not only does not answer it, it induces the person to take it to other cases that will deceive it, and it also gives a different example that does not fit what is asked in the question. Pass the idea that if there are 2 loops is O(n 2), which is a reasonable possibility, but it does not always occur in fact, which is what I demonstrated in the commentary.

  • 2

    I did not say that Bubble Sort can become O(n), I said that its model does not indicate what complexity should be, I gave an example that this is boring, I did not give an example that it works. So it’s a stuck model, a model can’t be used to/ prove something when time it works. Your answer is based on it. I did not say q your answer shows the wrong complexity, she is right (it just doesn’t have something to do with the question, but I understand to be another example, the intention was not to answer the question), I just said that she draws a conclusion that can’t happen, only the conclusion is fallacious

  • "I don’t understand why his complexity is considered O(nˆ2) instead of O(nˆ3)". That was the question. And I answered, in my own way.

Browser other questions tagged python

You are not signed in. Login or sign up in order to post.