finding the time complexity of the program

Question

How do we find the time complexity of below program? For the below program should the time complexity be O(N) or O(N*M) or O(N*M*M)?

Take-1: O(N)

• to scan N elements in the input array

Take-2: O(N*M)

• N is number of elements in the input array
• M is length of the longest email address in the list for split and find

Take-3: O(N*M*M)

• N is number of elements in the input array
• first M is length of the longest email address until @ in the list for split
• second M is length of the longest email address in the list for find

input_mails = ["[email protected]","[email protected]"] 
for email in input_mails: 
    first_part, second_part = email.split("@") 
    position = email.find(".")
    print(first_part)

Answer 1

The time complexity of the given program will be N*2M ~ O(N * M) where:

N: number of elements in the input array (input_mails)
M: length of the longest email address in the list

Here's how the operations contribute to the time complexity:

1. Looping through N elements in the input array: O(N)
2. Splitting each email address at @: O(M), as splitting depends on the length of the longest email address.
3. Finding the position of .: O(M), as finding the dot also depends on the length of the longest email address. Now, one point to note here is find() has the worst case time complexity of O(p*q) where p being the length of the longer string, q, the shorter string you search for. But since you mentioned you need to find dot(.) so q becomes 1 and for the context of your code it becomes O(M).

---

References and further reading:

1. Worst case time complexity of str.find() in python
2. Further reading around str.find()
3. Splitting and joining a string