How to find the recurrence relation T(N) = T(N/2) + N^2 -

-

what process involved in simplifying recurrence relation?

i able much:

t(n) = t(n/2) + n^2 t(n) = t(n/4) + (n/2)^2 +n^2 t(n) = t(n/8) + (n/4)^2 + (n/2)^2 + n^2

i understand terminate when n = 1 because 1/2 = 0; c(0) = 0. past stuck on way figure out these problems.

well basic idea c(n) , c(n/2) should expression of same form. since difference simple function of n, infinite sum should pop mind, c(n)-c(n/2) becomes telescopic. each term of sum should given function n/2^k (for k=0, 1, ...) argument.

hence c(n) = n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + ... job, , can further evaluated of identities geometric series c(n)=4/3*n^2.


Comments

Post a Comment

Popular posts from this blog

java - WrongTypeOfReturnValue exception thrown when unit testing using mockito -

-
my test list<person> mylist; @test public void testisvalidperson() { mylist = new arraylist<person>(); mylist.add(new person("tom")); when(persondao.get(person)).thenreturn(mylist); when((persondao.get(person)).isempty()).thenreturn(false);//------exception thrown boolean result = service.isvalid("tom"); assertfalse(result); } method tested: public boolean isvalid(string person){ persondao = new persondao(); person personobj = new person(person); return (persondao.get(person).isempty())?false : true; } exception thrown: org.mockito.exceptions.misusing.wrongtypeofreturnvalue: boolean cannot returned get() get() should return list *** if you're unsure why you're getting above error read on. due nature of syntax above problem might occur because: 1. exception *might* occur in wrongly written multi-threaded tests. please refer mockito faq on limitations of concurrency testing. 2. sp
Read more

php - Magento - Deleted Base url key -

-
i working on cleaning url: http://mydomain.com/shop/shop/deals i going through settings in configuration tab in admin panel on magento , change secure , unsecure base urls remove first base url "shop" web page read: http://mydomain.com/shop/deals so changed unsecure base urls mydomain.com/shop mydomain.com , secure 12.345.67.89/shop 12.345.67.89. wrong thing do. i cannot reload page or admin console. how access these files through ftp , change correctly there?? when make changes in admin panel changes made in database not in file. have make changes in database. 1.go database , select core_config_data table under table find web/unsecure/base_url , web/secure/base_url . make changes here. don't forget clear cache in var/cache folder
Read more

android - How to disable Button if EditText is empty ? -

-
i have edittext , button in application. when button clicked,the text entered in edittext added listview. i want disable button if edittext empty.how ? this code button click imagebutton imb=(imagebutton)findviewbyid(r.id.btn_send); imb.setonclicklistener(new onclicklistener() { @override public void onclick(view arg0) { edittext et = (edittext)findviewbyid(r.id.edittext1); string str = et.gettext().tostring(); web1.add(str); toast.maketext(shoutsingleprogram.this, "you entered...."+str, toast.length_short).show(); adapter1.notifydatasetchanged(); et.settext(""); } }); } how can ? edittext1.addtextchangedlistener(new textwatcher() { @override public void ontextchanged(charsequence s, int start, int before, in
Read more