big o - solving recurrence T(n) = T(n/2) + T(n/2 - 1) + n/2 + 2 -

-

need on solving runtime recurrence, using big-oh:

t(n) = t(n/2) + t(n/2 - 1) + n/2 + 2

i don't quite how use master theorem here

for n big enough can assume t(n/2 - 1) == t(n/2), can change

  t(n) = t(n/2) + t(n/2 - 1) + n/2 + 2

into 

  t(n) = 2*t(n/2) + n/2 + 2

and use master theorem (http://en.wikipedia.org/wiki/master_theorem) for

  t(n) = a*t(n/b) + f(n)    = 2   b = 2   f(n) = n/2 + 2   c = 1    k = 0    log(a, b) = 1 = c

and have (case 2, since log(a, b) = c)

  t(n) = o(n**c * log(n)**(k + 1))   t(n) = o(n * log(n))

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