LinearSearch example below, count each individual line as one step.def LinearSearch(A, x):
i = 0 # line 1
while i < len(A): # line 2
if A[i] = x: # line 3
return i # line 4
i = i + 1 # line 5
return -1 # line 6
LinearSearch executes 7 steps on input ([2,4,6,8],4), and 15 steps on input ([2,4,6,8],3).LinearSearch), size is measured in problem-appropriate fashion—like length of list A.^ | (number of steps) W | . | W . Each point represents number of steps | : : executed by algorithm on one input. | W . : 'W's correspond to worst-case runtime; | . : . 'B's correspond to best-case runtime; | W : . . average-case runtime falls somewhere | . . : : in between (depending on probability | W : : . . distribution over inputs). | : . . B B | W . B B | B B --------------------------> (input size)
Figure 12.1: Graph of Runtime Measures
LinearSearch on inputs of size n is 4:
x is first element in A, algorithm executes only lines 1–4.x does not appear in A, algorithm executes line 1, followed by lines 2, 3, 5 for each element in A, followed by line 2 (one last time) and line 6.LinearSearch(n).LinearSearch (3n+3), factor of "3" and term "+3" are artifacts of the way we count steps.LinearSearch.def LinearSearch(A, x):
i = 0 # line 1
while i < len(A): # line 2
if A[i] = x: # line 3
return i # line 4
i = i + 1 # line 5
return -1 # line 6
(A,x) to LinearSearch (with n = len(A)), loop in lines 2–5 executes constantly many steps, at most once for each value of i = 0,..,n-1, so T(n) ≤ an+b for some constants a,b, i.e., T(n) ∈ O(n).(A,x) be input to LinearSearch such that x ∉ A.A)).LinearSearch?# Precondition: A is sorted in non-decreasing order, i.e.,
# A[0] <= A[1] <= ... <= A[n-1] (where n = len(A)).
def BinarySearch(A, x):
b = 0
e = len(A)
# Invariant: if x appears in A, it appears in A[b:e] (A[e] excluded).
while b <= e:
m = (b + e) / 2
if x < A[m]: e = m
else: b = m
return b # if x appears in A, it appears at A[b]
x ∉ A, this happens at least that many times.LinearSearch is huge.def selection_sort(list):
''' Sort list in non-decreasing order, using Selection Sort. '''
# Invariant: list[0:i] is sorted, list[0:i] <= list[i:].
for i in range(len(list)):
# Find minimum element in list[i:].
m = i
# Invariant: list[m] <= list[i:j].
for j in range(i+1,len(list)):
if list[j] < list[m]: m = j
# Put minimum element at index i.
list[i], list[m] = list[m], list[i]
def insertion_sort(list):
''' Sort list in non-decreasing order, using Insertion Sort. '''
# Invariant: list[0:j] is sorted.
for j in range(1,len(list)):
# Find correct position for list[j] within list[0:j].
i = j
# Invariant: list[0:i] is sorted, list[i:j+1] is sorted,
# list[0:i] <= list[i+1:j+1].
while i >= 1 and list[i] < list[i-1]:
list[i-1], list[i] = list[i], list[i-1]
i -= 1
def merge_sort(list):
''' Sort list in non-decreasing order, using Merge Sort. '''
# If list contains at most 1 element, it is already sorted.
if len(list) <= 1: return
# Recursively sort each half of list.
middle = len(list) / 2
merge_sort(list[:middle])
merge_sort(list[middle:])
# Merge the sorted halves into a temporary list.
temp = []
left = 0
right = middle
# Invariant: 0 <= left <= middle <= right <= len(list), temp contains
# the merged contents of list[:left] with list[middle:right], every
# element in temp is less than or equal to every element in
# list[left:middle] and list[right:].
while len(temp) < len(list):
if right == len(list) or (left < middle and list[left] <= list[right]):
temp.append(list[left])
left += 1
else:
temp.append(list[right])
right += 1
# Copy the temporary list back into list.
list[:] = temp
import random
def quick_sort(list):
''' Sort list in non-decreasing order, using Quick Sort. '''
# If list contains at most 1 element, it is already sorted.
if len(list) <= 1: return
# Select a pivot element at random, then partition the list.
pivot = random.choice(list)
smaller = [x for x in list if x < pivot]
equal = [x for x in list if x == pivot]
greater = [x for x in list if x > pivot]
# Recurse and copy the results back into list.
quick_sort(smaller)
quick_sort(greater)
list[:] = smaller + equal + greater
| Algorithm | Worst-case | Average-case | Best-case | Notes |
|---|---|---|---|---|
| Selection Sort | Θ(n2) | Θ(n2) | Θ(n2) | depends only on size, not on particular input |
| Insertion Sort | Θ(n2) | Θ(n2) | Θ(n) | best for input already sorted (or close) |
| Merge Sort | Θ(n log n) | Θ(n log n) | Θ(n log n) | requires additional space Θ(n)—compared to Θ(1) for all others |
| Quick Sort | Θ(n2) | Θ(n log n) | Θ(n log n) | worst for input already sorted (or close) |
Table 12.1: Runtimes of Common Sorting Algorithms
lookup, insert, delete.| Data Structure | lookup |
insert |
delete |
|---|---|---|---|
| unsorted linked list | Θ(n) | Θ(1) | Θ(1) |
| unsorted array | Θ(n) | Θ(1) | Θ(1) |
| sorted array | Θ(log n) | Θ(n) | Θ(n) |
| binary search tree | Θ(n) | Θ(n) | Θ(n) |
| balanced search tree | Θ(log n) | Θ(log n) | Θ(log n) |
| hash tables | Θ(n) | Θ(n) | Θ(n) |
Table 12.2: Worst-case Complexity of Dictionary Operations
______50_________
/ \
20 ___75___
/ \ / \
10 30 60 90
\ / \ /
40 55 65 80
Figure 12.2: Binary Search Tree Example
lookup: start at root and follow order property down path until value is found or leaf is reached.insert: start at root and follow order property down path until leaf is reached, at which point it is added.delete: start at root and follow order property down path until value is found, at which point it is removed.
insert and delete operations.
insert or delete, trace path back up toward root.y right rotation x / \ --------------> / \ x C A y / \ left rotation / \ A B <------------- B C
Figure 12.3: Illustration of Tree Rotations
insert/delete.lookup: traverse linked list at index h(x).insert: add value to front of list at index h(x).delete: remove value from list at index h(x).insert and delete depend on runtime for lookup.
insert and delete is constant.
lookup?