Master method algorithm analysis of pseudocode -

-

how find c/d constant used in master theorem examining pseudo-code?

fastpower(a,b) :          if b = 1           return       otherwise           c := a*a           ans := fastpower(c,[b/2])       if b odd           return a*ans       otherwise return ans  end

firstly, need find recurrance relation: t(n) = t(n/b) + o(d) + o(c) o(d) time takes divide problem subproblems, o(c) time takes recombine subproblems answer, number of subproblems, , n/b size of subproblems. then, once have recurrence can analyze using master theorem.

in algorithm, believe there 1 subproblem of size n/2, 1 , b 2. time dividing o(1) , time recombining o(1) assuming analysis not in terms of bit operations.

using master theorem, o(1) = Θ(nlog21) therefore total runtime Θ(nlog21 log n) = Θ(log n)


Comments

Post a Comment

Popular posts from this blog

html5 - What is breaking my page when printing? -

-
Image
i have questioner , don't know why when printing it's creating break before first question. live demo (link) i able resolve issue removing fieldset container had wrapped in.. having fieldset element causing of fields grouped together, , since not fit on first page, being pushed second page. removing fieldset element, able firefox print first 2 questions on page 1 identically chrome. it seems not new problem firefox , fieldset not playing nice found old bugzilla ticket 2008 has persisted , still being commented on in 2014 (link) if retaining fieldset important, found solution else came here (link) <script type='text/javascript'> $(window).bind('beforeprint', function(){ $('fieldset').each( function(item) { $(this).replacewith($('<div class="fieldset">' + this.innerhtml + '</div>')); } ) }); $(window).bind(
Read more

c# - must be a non-abstract type with a public parameterless constructor in redis -

-
when save object, got below error must non-abstract type public parameterless constructor in order use parameter 't' in generic type or method 'servicestack.redis.redisclient.store<t>(t) redisclass.getinstnace().store(msg); // error here redisclass.getinstnace().save(); as third party's class, can not edit how save object? could create wrapper around third party object call constructor, store wrapper? e.g. public class mywrapper { public thirdpartyobject thirdpartyinstance { get; set; } public mywrapper() { thirdpartyinstance = new thirdpartyobject("constructors"); } }
Read more

ajax - PHP/JSON Login script (Twitter style) not setting sessions -

-
i'm having trouble getting twitter style login work properly, reason gets stuck at session_register("useremail"); session_register("userpass"); and doesn't redirect after it. if enter wrong account data, works , appropriate error message pops up. this full code: <?php if(empty($_post['email']) || empty($_post['password'])) { die(msg(0,"all fields required")); } if(!(preg_match("/^[\.a-z0-9_\-\+]+[@][a-z0-9_\-]+([.][a-z0-9_\-]+)+[a-z]{1,4}$/", $_post['email']))) die(msg(0,"you haven't provided valid e-mail")); $host="localhost"; $username="root"; $password="x"; $db_name="x"; $tbl_name="x"; mysql_connect("$host", "$username", "$password")or die("cannot connect"); mysql_select_db("$db_name")or die("cannot select db"); $useremail=$_post['email']; $userpass=
Read more