Time Complexity of Recursive Algorithms

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/5

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

6 Terms

1
New cards

Recursive Algorithms

Calls itself with smaller input values

Obtains the result for the current input by applying simple operations to the returned value for the smaller input

2
New cards

When to use Recursive Algorithms?

If a problem can be solved utilizing solutions to smaller versions of the same problem, and the smaller versions reduce to easily solvable cases

3
New cards

Back Substitution

<p></p>
4
New cards

Recursion Tree

  • Useful for visualizing what happens when a recurrence is iterated

  • It diagrams the tree of recursive calls and the amount of work done at each call

5
New cards

Master Theorem

<p></p>
6
New cards

When can you not use the Master Theorem?

  • T(n) is not monotone, e.g. T(n) = sin(x) 

  • f(n) is not a polynomial, e.g., T(n)=2T(n/2)+2^n 

  • b cannot be expressed as a constant