algorithm - Why Master theorem cannot be applied -

-

doing assignment , stuck on few questions.

  1. t(n) = t(2n/5)+n
  2. t(n) = t(2n/3)+t(n/3)+n
  3. t(n) = t(n−2)+n

something tells me on of them master theorem cannot applied. why? , upper bounds (big-oh)?

the master theorem can applied recurrence of form

t(n) = at(n / b) + o(nd)

where a, b, , d constants. (there other formulations, above 1 handles more common cases). specifically, means that

  • the problem size must shrink constant factor,
  • the subproblems must have same size,
  • there must constant number of subproblems, and
  • the additive term must polynomial.

these criteria rule out second recurrence (the subproblems don't have same sizes) , third (the problem size must shrink constant factor). however, first recurrence satisfies 4 of these criteria. might rewrite recurrence as

t(n) = t(n / (5/2)) + n.

based on that, case of master theorem in, , recurrence solve to?


Comments

Post a Comment

Popular posts from this blog

ios - MKAnnotationView layer is not of expected type: MKLayer -

-
Image
so code works fine logger riddled message. there way rid of or suppress it? postannotation.swift class postannotation: mkpointannotation { //mark: properties let post: post //mark: initialization init(post: post) { self.post = post super.init() self.coordinate = cllocationcoordinate2d(latitude: post.latitude, longitude: post.longitude) self.title = post.title self.subtitle = post.timestring() } } adding annotation let annotation = postannotation(post: post) self.map.addannotation(annotation) func mapview func mapview(_ mapview: mkmapview, viewfor annotation: mkannotation) -> mkannotationview? { if annotation mkuserlocation { return nil } var annotationview = mapview.dequeuereusableannotationview(withidentifier: "pin") as? mkpinannotationview if annotationview == nil { annotationview = mkpinannotationview(annotation: annotation, reuseidentifier: "pin")
Read more

ZeroMQ on Windows, with Qt Creator -

-
i have installed zmq link given below on windows 7. http://zeromq.org/distro:microsoft-windows 1) have c++ project in qt-creator , i'm using zmq c++ binding (zhelpers.hpp etc). 2) have added .lib installed zmq folder qtcreator 3) while compiling, compiler looks _imp__zmq_verion, in .dll files present in .lib have __imp_zmq_version. 4) causing undefined reference zmq_version. anyone else faced problem , has solution ?
Read more

unity3d - Unity SceneManager.LoadScene quits application -

-
i have 2 different scenes 1 named 'main' , other 'game' both added scenes in load. when use scenemanager.loadscene("game"); works no problem when tried return main scene code if (input.getkeydown (keycode.escape)) { scenemanager.loadscene("main"); } strangely game quits. thanks. sorry interruption. somewhere on other script found code. if (input.getkeydown (keycode.escape)) { application.quit (); } that's bad, know...
Read more