-1

I am confused with the time complexity of the following code and I need all the help I can get because I'm struggling to figure it out.

The code goes as follows:

def herhalen(s,p):
    pc = 0
    while pc < len(s):
       pd = pc + 1
       while pd < len(s):
          if s[pd] == s[pc]:
             x = 0
             while pd + x < len(s) and x < p and s[pc + x] == s[pd + x]:
                x += 1
             if x ==p:
                return True
          pd += 1
       pc += 1
    return False
DarrylG
  • 16,732
  • 2
  • 17
  • 23
Escaloetje
  • 11
  • 2
  • I have updated my answer and added the same code rewritten in a bit better way, which, however, helps to both easier understand time complexity and even find a bug! Remember to check out the difference between the snippets – Kolay.Ne Jan 25 '21 at 19:25
  • I would encourage you to use more **meaningful** variable names as well as more (or at least some) **comments**. This not only benefits you when you are going over your code in the future but it also helps the community of Stack Overflow to better understand *your* code. – alexandrosangeli Jan 25 '21 at 19:32

2 Answers2

1

Answer

Let's assume N is len(s)

The outer loop has O(N) complexity because pc takes all values from 0 to len(s) - 1. The second loop has the same complexity: although pd begins from pc + 1, not from 0, the two loops together will have the complexity O(N * N / 2) = O(N^2). The inner loop will have the O(min(N, P)) complexity (where P is the p variable from your function) because the loop will end either when pd + x reaches len(s) or when x reaches p

So, assuming P is not too small, if I am not mistaken, the overall complexity is O(N^3)

If you are having difficulties understanding why do the inner loops (starting from the outer loop iterable instead of 0) multiply complexity by N, not something smaller, please, see this question

Important note

By the way, I guess it would be much easier for you to understand the complexity by yourself if you were using for loops instead of whiles. I would rewrite the code in the following way (also contains some minor style improvements):

def herhalen(s, p):
    for pc in range(len(s)):
       for pd in range(pc + 1, len(s)):
          if s[pd] == s[pc]:
             for x in range(p):
                 if pd + x < len(s) or s[pc + x] == s[pd + x]:
                     break
             else:
                return True
    return False

Use all the power of the language you are writing in :)

Kolay.Ne
  • 1,345
  • 1
  • 8
  • 23
  • Thanks so much for your help :) – Escaloetje Jan 25 '21 at 21:25
  • @Escaloetje, oops, oh my god, I just figured out I was wrong. There was no bug in your code, it was my mistake when rewriting it. Sorry, I have updated the code, should work fine now – Kolay.Ne Jan 25 '21 at 21:52
1

It depends on the elements of s. If, for instance, all elements of s are equal, then your condition if s[pd] == s[pc] will always be true, which will in turn affect the overall complexity. If, however, all elements of s are distinct, then s[pd] == s[pc] will only be true when the pd and pc hold the same value and therefore pointing to the same element in s.

Example 1 - Unique elements

s = [i for i in range(20)] #[0,1,2,...,19]
pc = 0
while pc < len(s):
    pd = pc + 1
    while pd < len(s):
        if s[pd] == s[pc]:
            print(pd)
        pd += 1
    pc += 1

In this scenario, the print function is never executed.

Example 2 - Identical elements

s = [0 for i in range(20)] #[0,0,...,0]
pc = 0
print_counter = 1
while pc < len(s):
    pd = pc + 1
    while pd < len(s):
        if s[pd] == s[pc]:
            print(print_counter)
            print_counter += 1
        pd += 1
    pc += 1

In this scenario, the print function got executed 190 times which is O(n^2).

Note

  • Note that for your code, you have an additional loop that you have to consider.
  • Also note that there exist more scenarios where the elements of s are neither all equal or all unique.
alexandrosangeli
  • 262
  • 2
  • 13