CS61B Textbook
  • Contributors
  • DISCLAIMER
  • 1. Introduction
    • 1.1 Your First Java Program
    • 1.2 Java Workflow
    • 1.3 Basic Java Features
    • 1.4 Exercises
  • 2. Defining and Using Classes
  • 3. References, Recursion, and Lists
  • 4. SLLists
  • 5. DLLists
  • 6. Arrays
  • 7. Testing
  • 8. ArrayList
  • 9. Inheritance I: Interface and Implementation Inheritance
  • 10. Inheritance II: Extends, Casting, Higher Order Functions
    • 10.1 Implementation Inheritance: Extends
    • 10.2 Encapsulation
    • 10.3 Casting
    • 10.4 Higher Order Functions in Java
    • 10.5 Exercises
  • 11. Inheritance III: Subtype Polymorphism, Comparators, Comparable
    • 11.1 A Review of Dynamic Method Selection
    • 11.2 Subtype Polymorphism vs Explicit Higher Order Functions
    • 11.3 Comparables
    • 11.4 Comparators
    • 11.5 Chapter Summary
    • 11.6 Exercises
  • 12. Inheritance IV: Iterators, Object Methods
    • 12.1 Lists and Sets in Java
    • 12.2 Exceptions
    • 12.3 Iteration
    • 12.4 Object Methods
    • 12.5 Chapter Summary
    • 12.6 Exercises
  • 13. Asymptotics I
    • 13.1 An Introduction to Asymptotic Analysis
    • 13.2 Runtime Characterization
    • 13.3 Checkpoint: An Exercise
    • 13.4 Asymptotic Behavior
    • 13.6 Simplified Analysis Process
    • 13.7 Big-Theta
    • 13.8 Big-O
    • 13.9 Summary
    • 13.10 Exercises
  • 14. Disjoint Sets
    • 14.1 Introduction
    • 14.2 Quick Find
    • 14.3 Quick Union
    • 14.4 Weighted Quick Union (WQU)
    • 14.5 Weighted Quick Union with Path Compression
    • 14.6 Exercises
  • 15. Asymptotics II
    • 15.1 For Loops
    • 15.2 Recursion
    • 15.3 Binary Search
    • 15.4 Mergesort
    • 15.5 Summary
    • 15.6 Exercises
  • 16. ADTs and BSTs
    • 16.1 Abstract Data Types
    • 16.2 Binary Search Trees
    • 16.3 BST Definitions
    • 16.4 BST Operations
    • 16.5 BSTs as Sets and Maps
    • 16.6 Summary
    • 16.7 Exercises
  • 17. B-Trees
    • 17.1 BST Performance
    • 17.2 Big O vs. Worst Case
    • 17.3 B-Tree Operations
    • 17.4 B-Tree Invariants
    • 17.5 B-Tree Performance
    • 17.6 Summary
    • 17.7 Exercises
  • 18. Red Black Trees
    • 18.1 Rotating Trees
    • 18.2 Creating LLRB Trees
    • 18.3 Inserting LLRB Trees
    • 18.4 Runtime Analysis
    • 18.5 Summary
    • 18.6 Exercises
  • 19. Hashing I
    • 19.1 Introduction to Hashing: Data Indexed Arrays
      • 19.1.1 A first attempt: DataIndexedIntegerSet
      • 19.1.2 A second attempt: DataIndexedWordSet
      • 19.1.3 A third attempt: DataIndexedStringSet
    • 19.2 Hash Code
    • 19.3 "Valid" & "Good" Hashcodes
    • 19.4 Handling Collisions: Linear Probing and External Chaining
    • 19.5 Resizing & Hash Table Performance
    • 19.6 Summary
    • 19.7 Exercises
  • 20. Hashing II
    • 20.1 Hash Table Recap, Default Hash Function
    • 20.2 Distribution By Other Hash Functions
    • 20.3 Contains & Duplicate Items
    • 20.4 Mutable vs. Immutable Types
  • 21. Heaps and Priority Queues
    • 21.1 Priority Queues
    • 21.2 Heaps
    • 21.3 PQ Implementation
    • 21.4 Summary
    • 21.5 Exercises
  • 22. Tree Traversals and Graphs
    • 22.1 Tree Recap
    • 22.2 Tree Traversals
    • 22.3 Graphs
    • 22.4 Graph Problems
  • 23. Graph Traversals and Implementations
    • 23.1 BFS & DFS
    • 23.2 Representing Graphs
    • 23.3 Summary
    • 23.4 Exercises
  • 24. Shortest Paths
    • 24.1 Introduction
    • 24.2 Dijkstra's Algorithm
    • 24.3 A* Algorithm
    • 24.4 Summary
    • 24.5 Exercises
  • 25. Minimum Spanning Trees
    • 25.1 MSTs and Cut Property
    • 25.2 Prim's Algorithm
    • 25.3 Kruskal's Algorithm
    • 25.4 Chapter Summary
    • 25.5 MST Exercises
  • 26. Prefix Operations and Tries
    • 26.1 Introduction to Tries
    • 26.2 Trie Implementation
    • 26.3 Trie String Operations
    • 26.4 Summary
    • 26.5 Exercises
  • 27. Software Engineering I
    • 27.1 Introduction to Software Engineering
    • 27.2 Complexity
    • 27.3 Strategic vs Tactical Programming
    • 27.4 Real World Examples
    • 27.5 Summary, Exercises
  • 28. Reductions and Decomposition
    • 28.1 Topological Sorts and DAGs
    • 28.2 Shortest Paths on DAGs
    • 28.3 Longest Path
    • 28.4 Reductions and Decomposition
    • 28.5 Exercises
  • 29. Basic Sorts
    • 29.1 The Sorting Problem
    • 29.2 Selection Sort & Heapsort
    • 29.3 Mergesort
    • 29.4 Insertion Sort
    • 29.5 Summary
    • 29.6 Exercises
  • 30. Quicksort
    • 30.1 Partitioning
    • 30.2 Quicksort Algorithm
    • 30.3 Quicksort Performance Caveats
    • 30.4 Summary
    • 30.5 Exercises
  • 31. Software Engineering II
    • 31.1 Complexity II
    • 31.2 Sources of Complexity
    • 31.3 Modular Design
    • 31.4 Teamwork
    • 31.5 Exerises
  • 32. More Quick Sort, Sorting Summary
    • 32.1 Quicksort Flavors vs. MergeSort
    • 32.2 Quick Select
    • 32.3 Stability, Adaptiveness, and Optimization
    • 32.4 Summary
    • 32.5 Exercises
  • 33. Software Engineering III
    • 33.1 Candy Crush, SnapChat, and Friends
    • 33.2 The Ledger of Harms
    • 33.3 Your Life
    • 33.4 Summary
    • 33.5 Exercises
  • 34. Sorting and Algorithmic Bounds
    • 34.1 Sorting Summary
    • 34.2 Math Problems Out of Nowhere
    • 34.3 Theoretical Bounds on Sorting
    • 34.4 Summary
    • 34.5 Exercises
  • 35. Radix Sorts
    • 35.1 Counting Sort
    • 35.2 LSD Radix Sort
    • 35.3 MSD Radix Sort
    • 35.4 Summary
    • 35.5 Exercises
  • 36. Sorting and Data Structures Conclusion
    • 36.1 Radix vs. Comparison Sorting
    • 36.2 The Just-In-Time Compiler
    • 36.3 Radix Sorting Integers
    • 36.4 Summary
    • 36.5 Exercises
  • 37. Software Engineering IV
    • 37.1 The end is near
  • 38. Compression and Complexity
    • 38.1 Introduction to Compression
    • 38.2 Prefix-free Codes
    • 38.3 Shannon-Fano Codes
    • 38.4 Huffman Coding Conceptuals
    • 38.5 Compression Theory
    • 38.6 LZW Compression
    • 38.7 Summary
    • 38.8 Exercises
  • 39. Compression, Complexity, P = NP
    • 39.1 Models of Compression
    • 39.2 Optimal Compression, Kolmogorov Complexity
    • 39.3 Space/Time-Bounded Compression
    • 39.4 P = NP
    • 39.5 Exercises
Powered by GitBook
On this page
  • Example One:
  • Method 1: Count Number of Operations
  • Method 2: Geometric Visualization
  • Example 2:
  • Method 1: Finding the Bound Visually
  • Method 2: Finding the Bound Mathematically
  • Techniques: No Magic Shortcuts
  1. 15. Asymptotics II

15.1 For Loops

Count, count, count...

Previous15. Asymptotics IINext15.2 Recursion

Last updated 2 years ago

Now that we've seen some runtime analysis, let's work through some more difficult examples. Our goal is to get some practice with the patterns and methods involved in runtime analysis. This can be a tricky idea to get a handle on, so the more practice the better.

Example One:

Last time, we saw the function dup1, that checks for the first time any entry is duplicated in a list:

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;

We have two ways of approaching our runtime analysis:

  1. Counting number of operations

  2. Geometric visualization

Method 1: Count Number of Operations

Since the main repeating operation is the comparator, we will count the number of "==" operations that must occur.

Method 2: Geometric Visualization

We can also approach this from a geometric view.

Example 2:

Let's look at a more involved example next. Consider the following function, with similar nested for loops:

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;
      }
   }
}

The outer loop advances by multiplying i by 2 each time. The inner loop runs from 0 to the current value of i. The two operations inside the loop are both constant time, so let's approach this by asking "how many times does this print out "hello" for a given value of N?"

Our visualization tool from above helped us see dup1's runtime, so let's use a similar approach here. We'll lay out the grid for the nested for loops, and then track the total number of print statements needed for a given N below.

If N is 1, then i only reaches 1, and j is only 0, since 0 < 1. So there is only one print statement:

Conceptual Check: What happens when N = 3?

N = 3 will have the same number of print statements as N = 2.

The next change is at N=4, where there will be 4 prints when i = 4, 3 prints when i = 2, and 1 print when i = 1 (remember i never equals 3). So a total of 7.

We can keep filling out our diagram to get a fuller picture. Here it is up to N = 18:

What we see, if we add up all the counts at each stage of the loops, is that the number of print statements is:

(if N is a power of 2).

Again, we can think of this in two ways. Since we're already on a graphical roll, let's start there.

Method 1: Finding the Bound Visually

Method 2: Finding the Bound Mathematically

We can obtain the same result by solving our equation from above with the power of mathematics:

Again if N is a power of 2.

Techniques: No Magic Shortcuts

Unfortunately, they're not. And we know this because we just did two nested for loop examples above, each with different runtimes.

In the end, there is no shortcut to doing runtime analysis. It requires careful thought. But there are a few useful techniques and things to know:

  • Find exact sum

  • Write out examples

  • Draw pictures

We used each of these techniques above.

Also used in the examples above are two important sums you'll see very often:

You saw both of these above, and they'll return again and again in runtime analysis.

The first time through the outer loop, the inner loop will run N−1N-1N−1times. The second time, it will run N−2N-2N−2 times. Then N−3N-3N−3, N−4N-4N−4, .... all the way till running the inner loop exactly 111 time when i = N−1N - 1N−1. In the worst case, we have to go through every entry, and the outer loop runs NNN times.

Then, let CCC = total number of "==" operations that have occurred. The number of comparisons is:

C=1+2+3+...+(N−3)+(N−2)+(N−1)=N(N−1)/2C = 1 + 2 + 3 + ... + (N - 3) + (N - 2) + (N - 1) = N(N-1)/2C=1+2+3+...+(N−3)+(N−2)+(N−1)=N(N−1)/2

where N(N−1)/2N(N-1)/2N(N−1)/2 is part of the N2N^2N2 family.

Since "==" is a constant time operation, the overall runtime in the worst case is θ(N2)\theta(N^2)θ(N2).

Let's draw out when we use == operations in the grid of i,ji,ji,jcombinations:

We see that the number of == operations is the same as the area of a right triangle with a side length of N−1N - 1N−1. Since area is in the N2N^2N2​​ family, we see again that the overall runtime is θ(N2)\theta(N^2)θ(N2).

If N is 2, the next time through the loop i will be 1∗2=2,1*2 = 2,1∗2=2, and j can reach 1. The total number of print statements will be 3 = 1 (from first loop) + 2 (from second loop).

After the second loop, i=2∗2=4i = 2 * 2 = 4i=2∗2=4, which is greater than NNN, so the outer loop does not continue, and ends after i = 2, just like N = 2 did.

C(N)=1+2+4+...+NC(N) = 1 + 2 + 4 + ... + N C(N)=1+2+4+...+N

If we graph the trajectory of 0.5 N (lower dashed line), and 4N (upper dashed line), and C(N)C(N)C(N) itself (the red staircase line), we see that C(N) is fully bounded between those two dashed lines.

Therefore, the runtime (by definition) must also be linear: θ(N)\theta(N)θ(N).

C(N)=1+2+4+...+N=2N−1 C(N) = 1 + 2 + 4 + ... + N = 2N - 1C(N)=1+2+4+...+N=2N−1

For example, if N=8N = 8N=8 :

C(N)=1+2+4+8=15=2∗8−1C(N) = 1 + 2 + 4 + 8 = 15 = 2*8 - 1C(N)=1+2+4+8=15=2∗8−1

And by removing lesser terms and multiplicative constants, we know that 2N−12N - 12N−1 is in the linear family, so the runtime is θ(N)\theta(N)θ(N).

We now get a more exact value to the red-staircase line plotted below, which is 2N2N2N.

It would be really nice if there were some magic way to look at an algorithm and just know its runtime. And it would be even nicer if all nested for loops have a runtime of N2N^2N2 .

Sum of First Natural Numbers: 1+2+3+...+Q=Q(Q+1)/2=Θ(Q​2​​)1+2+3+...+Q=Q(Q+1)/2=Θ(Q ​2 ​​ ) 1+2+3+...+Q=Q(Q+1)/2=Θ(Q​2​​)

Sum of First Powers of 2: 1+2+4+8+...+Q=2Q−1=Θ(Q)1+2+4+8+...+Q=2Q−1=Θ(Q)1+2+4+8+...+Q=2Q−1=Θ(Q)

Visualizations when N = 1
Visualizations when N = 2
Visualizations for N = 18
Graph of 2N, bounded by 0.5N and 4N