python - What is the complexity of this recursive algorithm? -


does following algorithm have complexity of o(nlogn)?

the thing confuses me algorithm divides twice, not once regular o(nlogn) algorithm, , each time o(n) work.

def equivalent(a, b):      if isequal(a, b):         return true      half = int(len(a) / 2)     if 2*half != len(a):         return false      if (equivalent(a[:half], b[:half]) , equivalent(a[half:], b[half:])):         return true      if (equivalent(a[:half], b[half:]) , equivalent(a[half:], b[:half])):         return true      return false

each of 4 recursive calls equivalent reduces amount of input data factor of 2. thus, assuming a , b have same length, , isequal has linear time complexity, can construct recurrence relation overall complexity:

enter image description here

where c constant. can solve relation repeatedly substituting , spotting pattern:

enter image description here

what upper limit of summation, m? stopping condition occurs when len(a) odd. may anywhere between n , 1, depending on prime decomposition of n. in worse case scenario, n power of 2, function recurses until len(a) = 1, i.e.

enter image description here


Comments

Post a Comment

Popular posts from this blog

Is there a better way to structure post methods in Class Based Views -

i'm using class based views in django , never specify url in ajax calls , omit action parameter in form because know these requests go through post method of class based view. notice view - profile page make many requests depending on user updating on page - post method become convoluted , if/else mess example: def post(self, request, *args, **kwargs): # handle user changing available date if request.post.get('availabledate') != none: self.updateavailabledate(request) return jsonresponse({'result':'success'}) if request.post.get('newprojectname') != none: creative_user = creativeuserprofile.objects.get(id = request.user.id) project = project.create_project(creative_user, request.post['newprojectname']) project.save() return jsonresponse({'projectid': project.id }) if request.post.get('projectimage') != none , request.files['file']: proj...
Read more

reflection - How to access the object-members of an object declaration in kotlin -

say have following, nested object declaration: object father { val fathersfield = "value" object child { val childsfield = 3.141592654 } } when use reflection starting father , i'm able find field fathersfield no member referencing child instance. is possible find inner object declarations via reflection? , if so, how? use nestedclasses kotlin-reflect : father::class.nestedclasses.find { it.simplename == "child" } or, @s1m0nw1 suggested, use java reflection , convert class kclass .kotlin if needed: father::class.java.classes.first { it.simplename == "child" }.kotlin
Read more

php - Doctrine Query Builder Error on Join: [Syntax Error] line 0, col 87: Error: Expected Literal, got 'JOIN' -

i building shipping system ecommerce site using doctrine. have appropriate shipping methods , prices based on product , region data in checkout. i using following code querybuilder: $shippingpricereccords = $this->em->createquerybuilder() ->select('price') ->from('ordershippingprice', 'price') ->innerjoin('ordershippingmethod', 'method', 'price.fkordershippingmethod = method.id') ->innerjoin('ordershippingmethodregionmapping', 'map', 'map.fkordershippingmethod = method.id') ->where('price.fkproducttype = :fkproducttype') ->andwhere('price.fkbrand = :fkbrand') ->andwhere('map.fkregion = :fkregion') ->setparameters([ 'fkproducttype' => $fkproducttype, 'fkbrand' => $fkbrand, ...
Read more