Is the time complexity of this solution O(logn)?

user_10036828 0
Viewed 650

I have written the following solution for a challenge but I am not sure about its time complexity:

def ASCIIConversion(string): 
    newStr = ''

    for chr in string:
        if chr.isspace(): 
            newStr = newStr + ' '
        else:
            newStr += str(ord(chr))

    return newStr

Is the complexity of the program, O(logn), because of the else statement?

big-o time-complexity python
3 Answers

The time complexity in worst case is calculated as below(suppose string max length is n):

newStr = ''  # will be done once so 1 time.

for chr in string: # is iterating on the input with max length of n so n times.
    if chr.isspace(): # will be checked once it is in the loop so 1 time per each iteration.
        newStr = newStr + ' ' # also once per iteration if the if condition is satisfied
    else: # will be chehcked once per iteration
        newStr += str(ord(chr)) # if else is satisfied

return newStr # will be done 1 time.

we will assumes that the constant times are c so:

Time complexity = 1 + n(c*c + c*c) + 1 = 2+Cn => O(n)

user_107966590

This solution is still O(n). I'm not entirely sure why the else statement would affect this, actually. You're performing one operation on every character in the string.

Even though for each character, you're performing multiple instructions (comparisons, etc.), you may think the complexity is something like O(3n), but of course you disregard the coefficient. I'm sure you know this, but for people viewing this question in the future, confused about the else statement, this might help.

user_67963960

Irrespective of if-else condition, loop iterate through each character of string so time complexity is O(n).

user_62851340
Related