algorithm - Very simple recursive function complexity analysis -


i need understand analysing recursive algorithms. made algorithm up, , know complexity is:

int functionexampple( a1, a2, ... ) {     product = 1;     if( n == 2)     {         product = multi(a1, a2);     }     else      {         product = multi(a1, functionexample( a2, a3, ..., ) );    }    return product;  }

now assuming function multi takes o(n^1.59) time, complexity be? remain o(n^1.59) or recursive calls make o(n^1.59 * n ) account number of recursive calls? guys.

ps: wrote quickly, , syntax , stuff doesn't matter.

the parameter 'n' in o(n1.59) measures size(s) of arguments 'multi', not number of arguments. crucial how size of output 'multi' relates sizes of inputs. e.g. if result 'multi' twice size of of arguments, call multi(a, multi(b, c)) a, b, c of size n o(n1.59 + (2n)1.59), , if chain multiple calls multi in fashion exponential growth. on other hand, if 'multi' returns values of same size inputs, o(k n1.59) k number of arguments functionexample , n (largest) size.

so depends on how 'multi' behaves. e.g. there huge difference if multiplication versus multiplication within finite field, latter result wouldn't grow inputs, whereas unlimited integers result grows in size.


Comments

Post a Comment

Popular posts from this blog

jquery - Invalid Assignment Left-Hand Side -

i trying assign class tag via jquery, resulting in error through firebug says "invalid assignment left-hand side" on fourth line below. <cfoutput> $('.pngfix a').each(function(index) { var hreflink = $(this).attr("href"); if (hreflink.tolowercase() = '../audio.cfm') { $(this).addclass('audioimg'); } }); </cfoutput> looking around online, looks syntax problem, don't seem see it... any tips? thanks if (hreflink.tolowercase() = '../audio.cfm') that attempts assign value, rather check equality. change = operator == .
Read more

java - Play! framework 2.0: How to display multiple image? -

i need display gallery of photos. here template: @(photos: list[photo]) @title = { <bold>gallery</bold> } @main(title,"photo"){ <ul class="thumbnails"> @for(photo <- photos) { <li class="span3"> <a href="#" class="thumbnail"> <img src="@photo.path" alt=""> </a> </li> } </ul> } and here controller method: public static result getphotos() { return ok(views.html.photo.gallery.render(photo.get())); } and here photo bean : @entity public class photo extends model { @id public long id; @required public string label; public string path; public photo(string path, string label) { this.path = path; this.label = label; } private static finder<long, photo> find = new finder<long, photo>( long.class, photo.class); public static list<phot...
Read more

gmail - Is there any documentation for read-only access to the Google Contacts API? -

i want read-only access user's google contacts. there stackoverflow member wanted this, , received following answer : yes, there is, use https://www.googleapis.com/auth/contacts.readonly scope , "view contacts". this exchange reference read-only access google contacts can find using google. simply using access token obtained attempt read usual google contacts api (i.e. https://www.google.com/m8/feeds ) fails insufficient permissions. similarly, using google contacts api on new target fails 404 errors (for example https://www.googleapis.com/auth/contacts.readonly/default/full ). is there documentation anywhere on how use api, or permissible way access google contacts api full read-write access?
Read more