O-notation

Key operation

What is counted to estimate an algorithm’s running time. Most frequently executed instruction in an algorithm, or has the most impact on its running

What is the typical key operation for sorting and searching algorithms?

Item comparisons, ie calls to = or <=

Expression tightness

The expression 45n - 80 is both O(n) and O(n²) because it can be written as 0·n² + 45n - 80. O(n) is tighter than O(n²)

Name for O(n log n)

linearithmic

Name for O(n²)

quadratic

Name for O(2^n)

Exponential

How many comparisons does linear search do in the average and worst case?

O(n)

How many comparisons does insertion sort do in the average and worst case

O(n²) comparisons (quadratic time)

How many comparisons does insertion sort do in the best case?

O(n)

How many comparisons does quick sort do in the average and worst case?

O(n log n), O(n²) in the worst case

How many comparisons does merge sort do in the average and worst case

O(n log n)

How many comparisons does binary search do in the worst and average case

O(log n)