Algorithm Complexity – Lecture 21/22
Recall linkedlist.c append operation. Because a pointer to end of list is kept as tail,
statements -> time is O(1)
Induction is used when you have a claim that some property holds for all n >= 0 or 1,
where n is an integer. Call this claim P(n)
1. Prove base case – claim holds for n = 0 or n = 1
2. Show that P(n) implies P(n+1). Assume that P(n) is true, and prove that
a. Establishes an infinite implication… (-> means implies)
b. P(n) -> P(1) -> P(2) -> P(3)
Step 1 - Base case:
N = 1 ∑
Step 2 – Assume that P(n) is true. Show that P(n+1) is true
Step 1 – Base Case:
N = 1∑
Step 2 – Assume that P(n) is true. Prove for P(n+1) ∑
P(n) is n >= 2, then p – n is divisible by 3
Step 1 – Base Case
P(2) and 6 is divisible by 3.
Assume that P(n) is true -> n – n = 3r. r is some integer. Prove P(n+1)
P(n) is true because this is divisible by 3.
Induction assumed here.
Applications for Algorithms – Breadth First Search on a Grid
C , null )
Line above is Tuple representing coordinates (row/column) App