CSC236 recursive-runtime-I

Recurrence

A recursive function in mathematical notation

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

worst-case time

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

best-case time

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

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

Big theta 

Upper and lower bound for a run time function