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
  1. Format your code.
  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.

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

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