Time complexity for python code

Technical Discussions Python
#1

Hi,

Please can you tell the time complexity of below code.

def email_func(s):

f=s.find(’@’)
x=’’
y=’’
i=f
j=f-1
if f>0:

        while i<len(s) and s[i] != ' ':

             x+=s[i]
             i+=1

       while j>=0 and s[j] != ' ':

            y+=s[j]
            j-=1

       return y[::-1] + x

else: return False

x=email_func('abc@def ')
x

Instructions for code:

  • Define a function with the name email_func that takes a str argument and extracts out and returns the first email id. If there is no email id present return False .
  • Return only if there is valid email id. An email id is valid if at least one @ is present in it and no blank spaces. Else, you can return the boolean False. We are keeping the requirement for a valid email simple, requiring only one ‘@’ in it. We do not want you to write an exhaustive check for valid email here.
#2

Hi, Gaurav.

to find f=s.find(’@’) from string O(1) and to perform “while i<len(s)” it require O(len(s)).

  1. In worst case it require O(1)*O(len(s)) = O(len(s)). When the s has more string.

  2. In best case it require O(1)*0(1) =0(1) when s="@".

All the best!