CS61B, 2019
Lecture 15: Asymptotics II: Analysis of Algorithms
● Review of Asymptotic Notation
● Examples 1-2: For Loops
● Example 3: A Basic Recurrence
● Example 4: Binary Search
● Example 5: Mergesort
datastructur.es
Example 1/2:For Loops
Loops Example 1: Based on Exact Count
Find the order of growth of the worst case runtime of dup1. N= 6
int N = A.length;
for (int i = 0; i < N; i += 1)
for (int j = i + 1; j < N; j += 1) if (A[i] == A[j])
return true; return false;
==
==
==
==
==
==
==
==
==
==
==
==
==
==
==
0 1 2
i
3
4
5
Worst case number of == operations:
C = 1 + 2 + 3 + ... + (N - 3) + (N - 2) + (N - 1) = N(N-1)/2
012345 j
operation
worst case count
==
Θ(N2)
Worst case runtime: Θ(N2)
datastructur.es
Loops Example 1: Simpler Geometric Argument
Find the order of growth of the worst case runtime of dup1. N= 6
int N = A.length;
for (int i = 0; i < N; i += 1)
for (int j = i + 1; j < N; j += 1) if (A[i] == A[j])
return true; return false;
==
==
==
==
==
==
==
==
==
==
==
==
==
==
==
0 1 2
i
3
4
5
Worst case number of == operations:
● Given by area of right triangle of side length N-1.
● Area is Θ(N2).
012345 j
operation
worst case count
==
Θ(N2)
Worst case runtime: Θ(N2)
datastructur.es
Loops Example 2 [attempt #1]: http://yellkey.com/?
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)). By simple, we mean
there should be no unnecessary multiplicative constants or additive terms.
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
} }
}
Note that there’s only one case for this code and thus there’s no distinction between “worst case” and otherwise.
A. 1
B. log N C. N
D. N log N E. N2
F. Other
datastructur.es
Loops Example 2: Prelude to Attempt #2
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
0 1 2
i
3
4 5
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
Cost model C(N), println(“hello”) calls:
012345 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
N C(N)
datastructur.es
Loops Example 2: Prelude to Attempt #2
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
0 1 2
i
3
4 5
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
Cost model C(N), println(“hello”) calls:
012345 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
N C(N)
datastructur.es
Loops Example 2: Prelude to Attempt #2
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
0 1 2
i
3
4 5
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
Cost model C(N), println(“hello”) calls:
N C(N)
012345 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
3
datastructur.es
Loops Example 2: Prelude to Attempt #2
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
0 1 2
i
3
4 5
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
Cost model C(N), println(“hello”) calls:
012345 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
3
3
N C(N)
N=2 and 3 both print 3 times
datastructur.es
Loops Example 2: Prelude to Attempt #2
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
0 1 2
i
3
4 5
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
Cost model C(N), println(“hello”) calls:
N C(N)
012345 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
3
3
7
datastructur.es
Loops Example 2: Prelude to Attempt #2
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
0 1 2
i
3
4 5
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
Cost model C(N), println(“hello”) calls:
012345 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
3
3
7
7
7
7
N C(N)
N=4,5,6,7 all print 7 times
datastructur.es
Loops Example 2: Prelude to Attempt #2
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
0 1 2
i
3
4 5
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
Cost model C(N), println(“hello”) calls:
012345 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
3
3
7
7
7
7
15
15
15
15
15
15
15
15
N C(N)
These N all print 15 times
datastructur.es
Loops Example 2: Prelude to Attempt #2
public static void printParty(int N) { for (int i = 1; i <= N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
0 1 2
i
3
4 5
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
Cost model C(N), println(“hello”) calls:
012345 j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
3
3
7
7
7
7
15
15
15
15
15
15
15
15
31
31
31
N C(N)
C(N) = 1 + 2 + 4 + ... + N, if N is a power of 2
datastructur.es
Loops Example 2 [attempt #2]: http://yellkey.com/rangerange Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static void printParty(int N) { for (int i = 1; i<=N; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
A. 1
B. log N C. N
D. N log N E. N2
F. Other
Cost model C(N), println(“hello”) calls:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
3
3
7
7
7
7
15
15
15
15
15
15
15
15
31
31
31
N C(N)
C(N) = 1 + 2 + 4 + ... + N, if N is a power of 2
datastructur.es
Loops Example 2: Prelude to Attempt #3
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
N
1
4
7
8
27
185
715
C(N)
1
1 + 2 + 4= 7
1 + 2 + 4= 7
1 + 2 + 4 + 8 = 15
1 + 2 + 4 + 8 + 16 = 31
... + 64 + 128 = 255
... + 256 + 512 = 1023
0.5 N
0.5
2
3.5
4
13.5
92.5
357.5
2N
2
14
14
16
54
370
1430
datastructur.es
Loops Example 2 [attempt #3]:
http://yellkey.com/controlcontrol
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
NN
C(N)
0.5C(N)
2N
11
1
0.51
2
44
7
1 + 2 + 4
= 714
77
7
1+32.5+4
= 714
88
151+2+44+8=156
2277
311+2+143+.58+
165=431
118855 25...5 +6942+.5128=327505
771155 10...23+
253657+.512 =11403203
public static void printParty(int n) { for (int i = 1; i<=n; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
Cost model C(N), println(“hello”) calls:
● R(N) = Θ(1 + 2 + 4 + 8 + ... + N) if N is power of 2.
A. 1
B. log N C. N
D. N log N
E. N2
F. Something else
datastructur.es
Loops Example 2 [attempt #3]: http://shoutkey.com/TBA Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
R(N) = Θ(1 + 2 + 4 + 8 + ... + N) = Θ(N)
A. 1
B. log N C. N
D. N log N
E. N2
F. Something else
Can also compute exactly:
● 1 + 2 + 4 + ... + N = 2N - 1
● Ex: If N = 8
○ LHS: 1 + 2 + 4 + 8 = 15
○ RHS: 2*8 - 1 = 15
datastructur.es
Repeat After Me...
There is no magic shortcut for these problems (well... usually)
● Runtime analysis often requires careful thought.
● CS70 and especially CS170 will cover this in much more detail.
● This is not a math class, though we’ll expect you to know these:
○ 1 + 2 + 3 + ... + Q = Q(Q+1)/2 = Θ(Q2)
○ 1 + 2 + 4 + 8 + ... + Q = 2Q - 1 = Θ(Q)
Where Q is a power of 2.
← Sum of First Natural Numbers (Link) ← Sum of First Powers of 2 (Link)
public static void printParty(int n) { for (int i = 1; i <= n; i = i * 2) {
for (int j = 0; j < i; j += 1) { System.out.println("hello"); int ZUG = 1 + 1;
datastructur.es
Repeat After Me...
There is no magic shortcut for these problems (well... usually)
● Runtime analysis often requires careful thought.
● CS70 and especially CS170 will cover this in much more detail.
● This is not a math class, though we’ll expect you to know these:
○ 1 + 2 + 3 + ... + Q
○ 1 + 2 + 4 + 8 + ... + Q ● Strategies:
○ Find exact sum.
○ Write out examples.
○ Draw pictures.
= Q(Q+1)/2 = 2Q - 1
= Θ(Q2) = Θ(Q)
← Sum of First Natural Numbers (Link) ← Sum of First Powers of 2 (Link)
QR decomposition runtime, from “Numerical Linear Algebra” by Trefethen.
datastructur.es
Example 3: Recursion
Recursion (Intuitive): http://yellkey.com/personal Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1);
}
Using your intuition, give the order of growth of the runtime of this code as a function of N?
A. 1 4
B. log N
C. N
D. N2
E. 2N
33
2222
1111111
1
datas
tructur.es
Recursion (Intuitive)
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1);
}
Using your intuition, give the order of growth of the runtime of this code as a function of N? 5
A.14 4
2N: Every time we increase N by 1, we double the work!
B. log N C. N
D. N2
E. 2N
3333
22222222
111111111111111
1
datas
tructur.es
Recursion and Exact Counting
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1);
}
Another approach: Count number of calls to f3, given by C(N).
● C(1) = 1
● C(2) = 1 + 2
● C(3) = 1 + 2 + 4
4
33
2222
1111111
1
datas
tructur.es
Recursion and Exact Counting: http://yellkey.com/similar Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1);
}
Another approach: Count number of calls to f3, given by C(N). ● C(3) = 1 + 2 + 4
● C(N) = 1 + 2 + 4 + ... + ??? What is the final term of the sum?
4
33
2222
1111111
A. N B. 2N C. 2N-1
D. 2N-1 E. 2N-1-1
1
datas
tructur.es
Recursion and Exact Counting
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1);
}
Another approach: Count number of calls to f3, given by C(N).
● C(3) = 1 + 2 + 4
● C(N) = 1 + 2 + 4 + ... + ??? What is the final term of the sum?
D. 2N-1
4
33
2222
1111111
1
datas
tructur.es
Recursion and Exact Counting
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1);
}
Another approach: Count number of calls to f3, given by C(N). ● C(N) = 1 + 2 + 4 + ... + 2N-1
Give a simple expression for C(N).
4
33
2222
1111111
1
datas
tructur.es
Recursion and Exact Counting
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1);
}
Another approach: Count number of calls to f3, given by C(N). ● C(N) = 1 + 2 + 4 + ... + 2N-1
Give a simple expression for C(N).
● C(N) = 2N - 1
● Why? It’s the Sum of First Powers of 2.
4
33
2222
○ See next slide for details.
1111111
1
datas
tructur.es
Recursion and Exact Counting, Solving for C(N)
We know that the Sum of the First Powers of 2 from before, i.e. as long as Q is a power of 2, then:
Thus, since , we have that:
datastructur.es
Recursion and Exact Counting
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1);
}
Another approach: Count number of calls to f3, given by C(N).
● C(N) = 1 + 2 + 4 + ... + 2N-1
● Solving, we get C(N) = 2N - 1
Since work during each call is constant:
● R(N) = Θ(2N)
4
33
2222
1111111
1
datas
tructur.es
Recursion and Recurrence Relations
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1)
}
A third approach: Count number of calls to f3, given by a “recurrence relation” for C(N).
● C(1) = 1
● C(N) = 2C(N-1) + 1
4
33
2222
1111111
1
datas
tructur.es
Recursion and Recurrence Relations (Extra, Outside 61B Scope)
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1)
}
A third approach: Count number of calls to f3, given by a “recurrence relation” for C(N).
● C(1) = 1
● C(N) = 2C(N-1) + 1
More technical to solve. Won’t do this in our course. See next slide for solution.
4
33
2 2 2 2
1111111
1
datas
tructur.es
Recursion and Recurrence Relations (Extra, Outside 61B Scope)
Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).
This approach not covered in class. Provided for those of you who want to see a recurrence relation solution.
public static int f3(int n) { if (n <= 1)
return 1;
return f3(n-1) + f3(n-1)
}
One approach: Count number of calls to f3, given by C(N).
4
33
2222
1111111
1
datas
tructur.es
Example 4: Binary Search
Binary Search (demo: https://goo.gl/3VvJNw) Trivial to implement?
● Idea published in 1946.
● First correct implementation in 1962.
○ Bug in Java’s binary search discovered in 2006.
See Jon Bentley’s book Programming Pearls.
See
http://goo.gl/gQI0FN
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
datastructur.es
Binary Search (Intuitive): http://yellkey.com/daughter
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find runtime in terms of N = hi – lo + 1 [i.e. # of items being considered]
● Intuitively, what is the order of growth of the worst case runtime?
A. 1
B. log2 N
C. N
D. N log2 N
E. 2N
datastructur.es
Binary Search (Intuitive)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find runtime in terms of N = hi – lo + 1 [i.e. # of items being considered]
● Intuitively, what is the order of growth of the worst case runtime?
B. log2N
N ≈N/2 ≈N/4 ≈N/8
Why? Problem size halves over and over until it gets down to 1.
● If C is number of calls to binarySearch, solve for 1 = N/2C → C = log2(N)
datastructur.es
Example 4: Binary Search Exact (Optional) (see web video)
Binary Search (Exact Count): http://yellkey.com/enter
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items]
Cost model: Number of binarySearch calls.
N=6
●
What is C(6), number of total calls for N = 6?
A. 6 D. 2 B. 3 E. 1 C. log2(6)=2.568
datastructur.es
Binary Search (Exact Count)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items]
Cost model: Number of binarySearch calls.
● What is C(6), number of total calls for N = 6?
N=6
B. 3
3 calls N=3
N=1
Three total calls, where N = 6, N = 3, and N = 1.
datastructur.es
Binary Search (Exact Count)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items] ● Cost model: Number of binarySearch calls.
N C(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
1
3
N=1 datastructur.es
Binary Search (Exact Count)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items] ● Cost model: Number of binarySearch calls.
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
2
3
N C(N)
N=2 N=3
N=1
datastructur.es
Binary Search (Exact Count)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items] ● Cost model: Number of binarySearch calls.
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
2
3
3
3
3
N C(N)
4567
N=2 N=3
N=1
datastructur.es
Binary Search (Exact Count)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items]
● Cost model: Number of binarySearch calls.
N C(N)
8 9 …
4567
N=2 N=3
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
2
3
3
3
3
4
4
4
4
4
4
N=1
datastructur.es
Binary Search (Exact Count)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items]
● Cost model: Number of binarySearch calls. N
8 9 …
4567
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
2
3
3
3
3
4
4
4
4
4
4
C(N)
N=2
N=3
C(N) = ⌊log2(N)⌋+1
N=1
datastructur.es
Binary Search (Exact Count)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items]
8 9 …
● Cost model: Number of binarySearch calls.
● C(N) = ⌊log2(N)⌋+1 4
● Since each call takes constant time, R(N) = Θ(⌊log2(N)⌋)
○ This f(N) is way too complicated. Let’s simplify.
5 6
7
N=2
N=3
N=1
datastructur.es
Handy Big Theta Properties
Goal: Simplify Θ(⌊log2(N)⌋)
For proof:
See online textbook exercises.
● Three handy properties to help us simplify:
○ ⌊f(N)⌋=Θ(f(N)) [the floor of f has same order of growth as f]
○ ⌈f(N)⌉=Θ(f(N)) [the ceiling of f has same order of growth as f]
○ logP(N) = Θ(logQ(N)) [logarithm base does not affect order of growth]
⌊log2(N)⌋ = Θ(log N)
Since base is irrelevant, we omit from our big theta expression. We also omit the parenthesis around N for aesthetic reasons.
datastructur.es
Binary Search (Exact Count)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Goal: Find worst case runtime in terms of N = hi – lo + 1 [i.e. # of items]
8 9 …
● Cost model: Number of binarySearch calls.
● C(N) = ⌊log2(N)⌋+1 = Θ(log N) 4
● Since each call takes constant time, R(N) = Θ(log N)
… and we’re done!
5 6
7
N=2
N=3
N=1
datastructur.es
Binary Search (using Recurrence Relations)
static int binarySearch(String[] sorted, String x, int lo, int hi) if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi); else return m;
}
Approach: Measure number of string comparisons for N = hi – lo + 1.
● C(0) = 0
● C(1) = 1
● C(N) = 1 + C((N-1)/2)
Can show that C(N) = Θ(log N). Beyond scope of class, so won’t solve in slides.
datastructur.es
Log Time Is Really Terribly Fast
In practice, logarithmic time algorithms have almost constant runtimes.
● Even for incredibly huge datasets, practically equivalent to constant time.
N
log2 N
Typical runtime (seconds)
100
6.6
1 nanosecond
100,000
16.6
2.5 nanoseconds
100,000,000
26.5
4 nanoseconds
100,000,000,000
36.5
5.5 nanoseconds
100,000,000,000,000
46.5
7 nanoseconds
datastructur.es
Example 5: Mergesort
Selection Sort: A Prelude to Mergesort/Example 5
Earlier in class we discussed a sort called selection sort:
● Find the smallest unfixed item, move it to the front, and ‘fix’ it.
● Sort the remaining unfixed items using selection sort. Runtime of selection sort is Θ(N2):
● Look at all N unfixed items to find smallest. SS
● Then look at N-1 remaining unfixed. N=6 ●…
● Look at last two unfixed items.
● Done, sum is 2+3+4+5+…+N = Θ(N2)
6
3
7
2
8
1
1
3
7
2
8
6
1
2
7
3
8
6
1
2
3
7
8
6
1
2
3
6
8
7
…
datastructur.es
Selection Sort: A Prelude to Mergesort/Example 5
Earlier in class we discussed a sort called selection sort:
● Find the smallest unfixed item, move it to the front, and ‘fix’ it.
● Sort the remaining unfixed items using selection sort. Runtime of selection sort is Θ(N2):
SS ~36 AU N=6
● Look at all N unfixed items to find smallest.
● Then look at N-1 remaining unfixed.
●… SS
● Look at last two unfixed items.
● Done, sum is 2+3+4+5+…+N = Θ(N2)
~4096 AU N=64
Given that runtime is quadratic, for N = 64, we might say the runtime for selection sort is 4,096 arbitrary units of time (AU).
datastructur.es
The Merge Operation: Another Prelude to Mergesort/Example 5
Given two sorted arrays, the merge operation combines them into a single sorted array by successively copying the smallest item from the two arrays into a target array.
Merging Demo (Link)
datastructur.es
Merge Runtime: http://yellkey.com/report
2
3
6
10
11
4
5
7
8
2
3
4
5
6
7
8
10
11
How does the runtime of merge grow with N, the total number of items?
A. Θ(1) C.Θ(N) B. Θ(log N) D. Θ(N2)
datastructur.es
Merge Runtime: http://shoutkey.com/TBA
2
3
6
10
11
4
5
7
8
2
3
4
5
6
7
8
10
11
How does the runtime of merge grow with N, the total number of items?
C. Θ(N). Why? Use array writes as cost model, merge does exactly N writes.
datastructur.es
Using Merge to Speed Up the Sorting Process
Merging can give us an improvement over vanilla selection sort:
● Selection sort the left half: Θ(N2).
● Selection sort the right half: Θ(N2).
● Merge the results: Θ(N).
N=64: ~2112 AU.
● Merge: ~64 AU.
● Selection sort: ~2*1024 = ~2048 AU.
Still Θ(N2), but faster since N+2*(N/2)2 < N2
● ~2112 vs. ~4096 AU for N=64.
SS ~4096 AU N=64
M ~64 AU N=64
SS SS
~1024 AU
N=32
~1024 N=32
datastructur.es
Two Merge Layers
Can do even better by adding a second layer of merges.
SS
N=64
M ~64 N=64
MM
~4096 AU
Runtime for each sort:
● Selection sort only: ~4096 AU.
● One layer of merges: ~2112 AU.
● Two layers of merges: ~1152 AU.
○ Merge: ~64 AU + 2*~32 AU.
○ Selection sort: 4*~256.
~32 SS
N=32
~32 N=32 SS SS
SS
~256
16 16 16 16
datastructur.es
Example 5: Mergesort
Mergesort does merges all the way down (no selection sort):
● If array is of size 1, return.
● Mergesort the left half: Θ(??).
● Mergesort the right half: Θ(??).
● Merge the results: Θ(N).
Total runtime to merge all the way down: ~384 AU
● Top layer: ~64 = 64 AU
● Second layer: ~32*2 = 64 AU
● Third layer: ~16*4 = 64 AU
● Overall runtime in AU is ~64k, where k is the
number of layers.
● k = log2(64) = 6, so ~384 total AU.
SS ~4096 AU N=64
M 64 64
MM 32 32 32 32
k
MMM
16 16 16 16 16 16 ....
MM
8 8 8 8 ....
datastructur.es
...
Example 5: Mergesort Order of Growth, yellkey.com/job For an array of size N, what is the worst case runtime of Mergesort?
A. Θ(1)
B. Θ(log N)
C. Θ(N)
D. Θ(N log N)
E. Θ(N2)
N
k
N/2
N/2
N/4 N/4
N/8
N/4 N/4
....
N/8
N/8
N/8
....
datastructur.es
Example 5: Mergesort Order of Growth
Mergesort has worst case runtime = Θ(N log N).
● Every level takes ~N AU.
○ Top level takes ~N AU.
○ Next level takes ~N/2 + ~N/2 = ~N.
○ One more level down: ~N/4 + ~N/4 + ~N/4 + ~N/4 = ~N.
● Thus, total runtime is ~Nk, where k is the number of levels.
○ How many levels? Goes until we get to size 1.
○ k = log2(N).
N
● Overall runtime is Θ(N log N).
Exact count explanation is tedious.
● Omitted here. See textbook exercises.
N/2
N/2
k
N/4 N/4
N/8
N/4 N/4
....
N/8
N/8
N/8
....
datastructur.es
Mergesort using Recurrence Relations (Extra)
C(N): Number of calls to mergesort + number of array writes.
Only works for N=2k. Can be generalized at the expense of some tedium by separately finding Big O and Big Omega bounds (see next lecture).
N
k
N/2
N/2
N/4 N/4
N/8
N/4 N/4
....
N/8
N/8
N/8
....
datastructur.es
Linear vs. Linearithmic (N log N) vs. Quadratic
N log N is basically as good as N, and is vastly better than N2. ● For N = 1,000,000, the log N is only 20.
(from Algorithm Design: Tardos, Kleinberg)
datastructur.es
Summary
Theoretical analysis of algorithm performance requires careful thought.
● There are no magic shortcuts for analyzing code.
● In our course, it’s OK to do exact counting or intuitive analysis.
○ Know how to sum 1 + 2 + 3 ... + N and 1 + 2 + 4 + ... + N.
○ We won’t be writing mathematical proofs in this class.
● Many runtime problems you’ll do in this class resemble one of the five
problems from today. See textbook, study guide, and discussion for more
practice.
● This topic has one of the highest skill ceilings of all topics in the course.
Different solutions to the same problem, e.g. sorting, may have different runtimes.
● N2 vs. N log N is an enormous difference.
● Going from N log N to N is nice, but not a radical change.
datastructur.es