# Time complexity

I wrote a simple program, but I am confused about its time complexity. Here is the code:-

def makgood(st,ch,n):
if n==1:
if st==ch:
return 0
else:
return 1
k=int(n/2)
a=st[:k].count(ch)
b=st[k:].count(ch)
nx=chr(ord(ch)+1)
c=min((k-b+makgood(st[:k],nx,k)),k-a+makgood(st[k:],nx,k)) 

Thanx in advance
2. What is the function f(n/2)

Ohh sorry I forgot to mention f=int

It seems that spaces are removed automatically. Sorry for the trouble.

@gaurav822002 This might help in formatting your code [Tutorial] CoLoR format the Code!

Let T(n) denote time complexity for the input of n elements.
Here, the .count() functions takes O(m) time for m elements.
For every recursive level with k elements, you recur again for \frac{k}{2} elements twice.
Hence,
T(n) = 2T(\frac{n}{2}) + O(n)
Solving it gives the final time complexity as \boxed{O(n \log_2n)}

2 Likes

to correctly format your code you should use  instead of ´´´.

1 Like