algorithm - Recurence related to master theorem T(n)=T(n^(1/2))+1 -


in masters theorem given "plug-in" formula find big o, given satisfies condition.

however, if have problems following below? can show me how step step formula. , topics me know more these types of questions. assume person asking question knows nothing induction. 

t(n)=t(n^(1/2))+1 t(n)=t(n-1) + 1 t(n)=t(n-1) + n^c , c natural number >1 t(n)= t(n-1) c^n, c natural number >1

you'll need know little math of these. can figure out recursion looks when expand out way base case, e.g. t(n) = t(n-1) + n^c t(n) = 1^c + 2^c + ... + n^c, need know math in order know o(n^(c+1)). (the easiest way see bounding sum above , below in terms of integrals of x^c). t(n) = t(n-1) + c^n t(n) = c^1 + c^2 + ... + c^n again need use calculus or figure out t(n) = o(c^n).

for t(n) = t(n^(1/2)) + 1 need count how many times apply recurrence before base case. again math helps here. when take square-root, logarithm gets cut in half. want know how many times can cut logarithm in half until base case. o(log log n).


-

Comments

Post a Comment

Popular posts from this blog

php - regexp cyrillic filename not matches -

i take list of files php glob(."*.pdf") . files have cyrillic names. example: ООО «Рога и копыта» then load company names database , try find them in file names: preg_match("/$firm_name/ui", $file_name, $match); i have problem: firms if $firm_name visually similar $file_name , preg_match says there no match. mb_detect_encoding both variables return utf-8. there problem in file name, or maybe there encoding or something, can not understand, ask help. upd: $file_name='ООО «Рога и копыта»'; preg_match("/... .Рога и копыта./ui", $file_name, $match); as result, ОО «Рога и копыта» , 1 О missing
Read more

c# - OpenXML hanging while writing elements -

Image
i have program pulls data database, caches file , exports data multiple formats (excel, excel 2003, csv). i'm using openxml sdk 2.0 excel work. these export processes run in parallel (using parallel.foreach ), , amount of data can pretty large - e.g. csvs 800mb. during these larger exports, i've noticed writing of xml documents hang. instance, if have 8 exporting in parallel, @ point "pause". hang around same point: //this.writer openxmlwriter created worksheetpart. this.writer.writeelement(new cell() { cellvalue = new cellvalue(value), datatype = cellvalues.string }); when happens, pause debugger (vs2013 in case) , notice threads blocking around same portion of code - bit deeper in openxml sdk - stem call openxmlwriter.writeelement . i dug through source using justdecompile didn't find answers. appears there intermediary stream in use writing isolated storage , is, reason, blocking. underlying stream each of these filestream . here screenshot ...
Read more

sql - Select Query has unexpected multiple records (MS Access) -

i may tired, can't seem figure out happening. have 2 queries. query 1 has 10 fields. query 2 has 5 fields. fields 1 through 3 same in both queries. trying write select query , simple add field 5 query2 query1 result should query1 additional field (query2.field5). i join first 3 fields both queries , choose select records in query1 , in query2 match. don't know sql, use query designer. expect same number of records have query 1 instead have 3 times or more. can tell me doing wrong. tried reversing joins still seem same records. thanks in advance. here query: the fields in common divisionname , supplierid = vendorid , commodityname . select [part revenue exposed query p1].divisionname, [part revenue exposed query p1].commodityname, [part revenue exposed query p1].suppliername, [part revenue exposed query p1].partnumber, [part revenue exposed query p1].partdescription, [part revenue exposed query p1].bucode, ...
Read more