CODEWITHSUNDEEP
pythontime-complexity
user2773013
user2773013

Reputation: 3172

time complexity of a double for loop

I'm trying to ask myself what is the time and space complexity of the following code. This is intended to spit out anagram from a list of words.

def ana(input_):
    results = []
    for key, word1 in enumerate(input_):
        a=set([i for i in word1])
        for word2 in input_[key+1:]:
            b=set([i for i in word2])
            if len(set(a)-set(b))==0 and len(set(b)-set(a))==0:
                if word1 not in results:
                    results.append(word1)
                if word2 not in results:
                    results.append(word2)

For time complexity, the first for loop indicate there is at least N iteration. I'm confused with the second for loop. It's definitely less than N, but more than log N. How should this be noted?

In term of space complexity: this is just O(N) to store the results. Is this correct?

Upvotes: 0

Views: 246

Answers (1)

MisterMiyagi
MisterMiyagi

Reputation: 52149

TLDR: A nested loop of the size N - 1 + N - 2 + ... + N - N is still O(N^2).

The outer loop iterates through input_ completely -- for a size N input_ the loop contributes a factor of O(N). That means the function is at least O(N) in total.

The inner loop iterates through input_[key+1:], with key ranging from 0 to N - 1. That means in the first iteration it has O(N), but for the last iteration it has O(1). That means the function is between O(N^2) and O(N) in total.

You can quickly estimate the complexity now already. The first few inner iterations contribute O(N) + O(N - 1) + ... and so on. Even if we look at the first half of all iterations, the last of these still contributes O(N/2). Since O(N - 1) = O(N) and O(N/2) = O(N) we definitely have N/2 loops of O(N) each. That gives O(N / 2 * N) = O(N^2) complexity.

You can also calculate the iterations accurately -- this situation is similar to triangular numbers. The inner loop performs a total of (N - 1) + (N - 2) + ... + (N - N + 1) + (N - N) iterations. This can be re-ordered to ((N - 1) + (N - N)) + ((N - 2) + (N - N + 1)) + ... i.e. pairs of lowest/largest remaining.

  • Each pair has the value (N - 1 + N - N) or just (N - 1).
  • Rearranging our initial N terms into pairs means we have N / 2 pairs.

This means the sum of all pairs is (N - 1) * N / 2.

In other words, the inner loop does a total of (N - 1) * N / 2 iterations. That is O((N - 1) * N / 2) = O(N * N) = O(N^2) complexity.

Upvotes: 1

Related Questions