CSC236 recursive-runtime-I

0.0(0)
studied byStudied by 0 people
0.0(0)
full-widthCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
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

Recurrence

A recursive function in mathematical notation

2
New cards

Unrolling (repeated substitution)

Unrolling means you write out the first few levels of the recursion explicitly to see the pattern

EX:

T (4) = 1 + T (3)
= 1 + 1 + T (2)
= 1 + 1 + 1 + T (1)
= 1 + 1 + 1 + 1 + T (0)
= 1 + 1 + 1 + 1 + 1
= 5

3
New cards

worst-case time

measure the set of times. Using the maximum is called the Worst-Case time

4
New cards

best-case time

measure the set of times, using the minimum is called the Best-Case time

5
New cards

average case time

measure the set of timesm using an average based on some probability distribution of inputs is a called an Average-Case time

6
New cards

Big theta 

Upper and lower bound for a run time function

<p>Upper and lower bound for a run time function</p>