CSC236H5 Lecture Notes - Lecture 5: University Of Toronto Mississauga, Big O Notation, Mathematical Induction
16 Oct 2017
School
Department
Course
Professor
Document Summary
What can we say about the asymptotic runtime of the above two algorithms? bounds are the same: their b) c, there is not enough information here to say fact1 is faster fact2 is faster. T n recursive calls, each one does constant amount of work: heta(n) You should be able to notice that there is only n recursive calls which makes the work done. Which of the following is the worst-case recurrence for the above function? a. b. 4th step: consider the + in the return statement. you need to consider that in the amount of work. What if the d value is not needed? def . , the worst-case runtime for input size n (n)t. (week 4) bound from the closed-form (week 3) bound is as follows: Another way to find the bound for a recursive algorithm: bound. Use simple/complete induction to prove the . N=2 by the recursive definition, n lg n.
