big o - Complexity of factorial recursive algorithm -

-

today in class teacher wrote on blackboard recursive factorial algorithm:

int factorial(int n) {    if (n == 1)         return 1;    else         return n * factorial(n-1); }

she said has cost of t(n-1) + 1.

then iteration method said t(n-1) = t(n-2) + 2 = t(n-3) + 3 ... t(n-j) + j, algorithm stops when n - j = 1, j = n - 1.

after that, substituted j in t(n-1) + 1, , obtained t(1) + n-1.

she directly said n-1 = 2(log2n-1), cost of algorithm exponential.

i lost last 2 steps. can please explain them me?

let's start off analysis of algorithm. can write recurrence relation total amount of work done. base case, 1 unit of work when algorithm run on input of size 1, so

t(1) = 1

for input of size n + 1, algorithm 1 unit of work within function itself, makes call same function on input of size n. therefore

t(n + 1) = t(n) + 1

if expand out terms of recurrence, that

  • t(1) = 1
  • t(2) = t(1) + 1 = 2
  • t(3) = t(2) + 1 = 3
  • t(4) = t(3) + 1 = 4
  • ...
  • t(n) = n

so in general algorithm require n units of work complete (i.e. t(n) = n).

the next thing teacher said that

t(n) = n = 2log2 n

this statement true, because 2log2x = x nonzero x, since exponentiation , logarithms inverse operations of 1 another.

so question is: polynomial time or exponential time? i'd classify pseudopolynomial time. if treat input x number, runtime indeed polynomial in x. however, polynomial time formally defined such runtime of algorithm must polynomial respect number of bits used specify input problem. here, number x can specified in θ(log x) bits, runtime of 2log x technically considered exponential time. wrote length in this earlier answer, , i'd recommend looking @ more thorough explanation.

hope helps!


Comments

Post a Comment

Popular posts from this blog

Perl - how to grep a block of text from a file -

-
it can in xml or text format. how in general grep block of text in perl? <track type="ws"> <range> <rangestart>0</rangestart> <rangeend>146.912</rangeend> <locationindex>0</locationindex> <propertyindex>0</propertyindex> </range> </track> <track type="ps" id="1"> <range> <rangestart>0</rangestart> <rangeend>146.912</rangeend> <locationindex>1</locationindex> <propertyindex>1</propertyindex> </range> </track> i want grep type="ps" , till </range> . one solution open file, read line line , match block. open(fh, "file.txt"); foreach $line (<fh>) { if ($line =~ m/type="cc"(.*?)<\/range>/) { print $1; } } but there more optimal solution without reading file line l
Read more

delphi - How to remove all the grips on a coolbar if I have several coolbands? -

-
Image
if set mycoolbar.fixedorder true,only grip on first band hidden. well,if use delphi 7 create vcl forms application,then put coolbar on , create 3 coolbans hold other controls,only grip , top coolbands can hidden setting mycoolbar.fixedorder:=true. i've uploaded picture make things clear. you got fixedorder property wrong. fixed property not allow bands rearranged if set true . setting property of coolbar true keep user changing bands order @ runtime, user can still move , resize bands. can give advice can do, actual solution problem, well, have wait answer. my advice use 3 coolbars in row , setting "fixedorder" property true , bandborderstyle bsnone . way grip hidden on of them. about property, it's not bug of ide, actual preference of property.
Read more

javascript - Animating array of divs; only the final element is modified -

-
this baffling me @ moment. i'm experienced programmer looking throw bit of surprise fiancee on countdown page our wedding. desired effect simulated confetti falling behind main page. setup follows: i have array of divs in javascript. each div absolutely positioned on page. have interval set updates every 50 or milliseconds. on each tick, run loop on array of divs, , calculations , update positions. problem problem having, however, though can see divs created, stored array, , modified (in case, each has slight randomized rotation) during initialization phase, once tick update position starts, div stored in whatever last slot of array gets position updated. tried hard-coding each div index testing purposes, strictly last element update position. upon printing current "left" , "top" style values each div before , after calculations shows value has been changed, no visible change noticeable. here's basic code: javascript var container;
Read more