[FIXED] What time complexity does the following code have?

Issue

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

Solution

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.

Answered By - alexandrosangeli