CODEWITHSUNDEEP
pythonalgorithmtime-complexity
Shubham Gaikwad
Shubham Gaikwad

Reputation: 123

Find the time complexity of nested loops

I want to find the time complexity of my_func(). Input to this function is a list of integers. Length of the list is N.

Code:

def my_func(lst: List[int], N: int):
    if N < 4:
        return 0
    else:
        lim = int(N/2) + 1
        for p_len in range(2, lim): # outer for loop
            pattern = lst[:p_len]
            for i in range(p_len, N, p_len): # inner for loop
                if pattern != lst[i:i+p_len]:
                    break
            else:
                return 1 
        return 0

My Analysis:
Inner for loop runs N/p_len times. Outer for loop runs N/2 times. Hence,

T(n) = N/1 + N/2 + N/3 + ... + N/(N/2)
T(n) = N(1/1 + 1/2 + ... + 1/(N/2)
T(N) = N log (N/2)
T(N) = O(n log n)


Is this a correct analysis?

Upvotes: 0

Views: 695

Answers (2)

OmG
OmG

Reputation: 18858

The following analysis shows the time complexity of the algorithm:

Based on the comments, in the worst case, inside the inner loop will run in O(p_e) which is the number of comparisons of the pattern with the whole of the list. p_e in the above equation is equal to p_{len}. We know that the inner loop will iterate n/p_e times (as the step of increasing is n/p_e).

Upvotes: 0

superb rain
superb rain

Reputation: 5531

Worst case is like [0]*(N-1) + [1], where the outer loop runs N/2 times and the inner loop checks the pattern against the whole list, so the inner loop takes O(N) and thus your total time is only O(N2).

In other words, you're right that the inner for loop runs (up to) N/p_len times, but you forgot that each time takes O(p_len). Neither slice creation nor slice comparison are O(1). So you have (N/p_len)*p_len=N for the inner loop.

Upvotes: 1

Related Questions