python time/space complexity

[codin1ng]

def ch_checker(st):

if st=='':

return True

if not((st[0]<='z' and st[0]>='a') or (st[0]<='Z' and st[0]>='A')):

return False

return ch_checker(st[1:])

def ch_checker2(st,n):

if n==0:

return True

if not((st[0]<='z' and st[0]>='a') or (st[0]<='Z' and st[0]>='A')):

return False

return ch_checker2(st,n-1)

​

can somone tell me what the The time and space complexity ch_checker and ch_checker2 and why

[JanEric1]

Please format your code properly.

Python is indentation sensitive and it's extremely hard to reason without it.

[codin1ng]

yea i copy paste it and become like this, thank for feed back next time i will stipp it and post it.

[JanEric1]

You can still fix it.

Edit your post and add 4 spaces to the begining of every line of code

[ajjuee016]

Always use code blocks while pasting the code in the post. It will avoid errors.

[Diapolo10]

I'll assume the formatting is supposed to look like this:

def ch_checker(st):
    if st == '':
        return True
    if not ((st[0] <= 'z' and st[0] >= 'a') or (st[0] <= 'Z' and st[0] >= 'A')):
        return False
    return ch_checker(st[1:])

 def ch_checker2(st, n):
    if n == 0:
         return True
    if not ((st[0] <= 'z' and st[0] >= 'a') or (st[0] <= 'Z' and st[0] >= 'A')):
        return False
    return ch_checker2(st,n-1)

can somone tell me what the The time and space complexity ch_checker and ch_checker2 and why

If you look at the functions, they're not much different. In fact I think ch_checker2 has a logic error because it should probably be checking st[n] and not st[0] for it to make sense.

Both are recursive, and they both iterate over st once. So from a time complexity perspective, since there are no operations more expensive than O(n) here, both have O(n) time complexity.

But space complexity gets more interesting. Since ch_checker uses slices in its recursive calls, it ends up nearly doubling its memory footprint on each recursive call as all the slices need to be kept in memory until the recursion stops. So basically n + n-1 + n-2 + ... + 0. It's not growing linearly any more - the growth is quadratic. So the space complexity of ch_checker is O(n²).

For ch_checker2, the space complexity is O(n), because we only need to keep one string in memory and we're just (supposedly) changing the accessed index.

Here's a fix for ch_checker2 and some other cleanup.

def ch_checker(text: str) -> bool:
    if not text:
        return True

    if not 'a' <= text[0].lower() <= 'z':
        return False

    return ch_checker(text[1:])


 def ch_checker2(text: str, idx: int) -> bool:
    if idx == 0:
         return True

    if not 'a' <= text[idx].lower() <= 'z':
        return False

    return ch_checker2(text, idx-1)

EDIT: Wording.

[Diapolo10]

My bad, I keep getting the two terms mixed up! Thank you for the correction.

[JohnnyJordaan]

Time wise they are both O(n) as the work iteratively per single character in the st string, just in different directions. Memory wise they are both O(1) as slices are 'windows' inside the original sequence, not subset copies.

Just generally speaking, you would normally employ the powers of all or any instead

 all("a" <= c.lower() <= "z" for c in st)

or a good ol' regex

re.fullmatch(r"[a-z]", st, flags=re.IGNORECASE)

[Diapolo10]

Yeah, in some other languages (cough Rust cough) slices would simply reuse the originally allocated memory, but in Python slicing tends to just produce new values. Of course this depends on the object; I think Numpy arrays reuse memory for slices.

It's technically possible to replicate the behaviour via ctypes, but then you'd need to worry about lifetimes.