Time and Space Complexity

Read Section 5.1.1 of Bailey (p. 81–85 of the text, 97–101 of the pdf). See the rest of Section 5.1 for examples and additional discussion.

Here is a video lecture for the slides below.

The video contains sections on

1. Learning Objectives (0:20)
2. Time and space analysis helps us differentiate (1:10)
3. We need a tool to analyze code that is (3:56)
4. Overview: Algorithmic Analysis (6:13)
5. What is a Complexity Class (7:34)
6. Does Complexity Really Matter? (9:58)
7. Code Modeling (11:23)
8. What is an operation? (11:38)
9. Code Modeling Example I (13:54)
10. Code Modeling Example II (16:19)
11. Finding a Big-O (19:21)
12. Is it okay to throw away all that info? (21:46)
13. No seriously, this is really okay? (24:15)
14. Using Formal Definitions (27:16)
15. Big-O Definition (28:41)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=6ee55f38-7708-4db6-8b57-acb8013c47f8

You can download the slides in pdf or PowerPoint.

1. Model the number of operations involved in the following code in terms of \(n\):

   public int method1(int n) {
       int sum = 0;
       for (int i = n; i > 0; i -= 2) {
           for (int j = 0; j < n; j++) {
               sum++;
           }
       }
       return sum;
   }
   

2. Model the number of operations involved in the following code in terms of \(n\):

   public int method2(int n) {
       int sum = 0;
       for (int i = 1; i <= n * 2; i++) {
           for (int j = 1; j <= n; j++) {
               sum++;
           }
       }
       for (int j = 1; j < 100; j++) {
           sum++;
           sum++;
       }
       return sum;
   }
   

3. Model the number of operations involved in running bar in terms of \(n\):

   public boolean foo(int x) {
       return x % 2 == 0 && x > 0;
   }
   
   public int bar(int n) {
       int sum = 0;
       for (int i = 0; i < n; i++) {
           if (foo(i)) {
               sum += i;
           }
       }
       return sum;
   }
   

4. Give the big-O complexity for problems 1, 2, and 3.
5. Suppose an algorithm takes exactly the given number of statements for each value below, in terms of an input size \(n\). Give the big-O bound for each algorithm, representing the closest complexity class for that algorithm based on that runtime.
   1. \(3n\)
   2. \(n + 900\)
   3. \(\frac{1}{2}n\log n + \log n\)
   4. \(n^2 - (n + n\log n + 1000)\)
   5. \(n^2 \log n + 2n\)
   6. \(\frac{1}{2}(3n + 5 + n)\)
   7. \((2n + 5 + n^4)/n\)
   8. \(n! + 2n\) (\(n!\) is \(n\)-factorial, meaning the product \(n \times (n - 1) \times (n - 2) \cdots 2 \times 1\))

• share confusions/questions in learning pods
• questions?
• form question
• practice problem 5
• timing demo

  import java.util.ArrayList;
  import java.util.LinkedList;
  
  import edu.princeton.cs.algs4.StopwatchCPU;
  
  public class Timing {
      public static void main(String[] args) {
          StopwatchCPU watch = new StopwatchCPU();
  
          // compare O(n) with O(1)
          int n = 100000;
          int[] nums = new int[n];
          double start = watch.elapsedTime();
          for (int i = 0; i < nums.length; i++) {
              nums[i] = i;
          }
          double end = watch.elapsedTime();
          System.out.println("loop took " + (end - start) + "s");
  
          start = watch.elapsedTime();
          nums[0] = 100;
          end = watch.elapsedTime();
          System.out.println("one assignment took " + (end - start) + "s");
  
          ArrayList<Integer> arraylist = new ArrayList<>();
          LinkedList<Integer> linkedlist = new LinkedList<>();
          start = watch.elapsedTime();
          // O(n^2)
          for (int i = 0; i < nums.length; i++) {
              // linear time insertion into arraylist
              arraylist.add(0, i);
          }
          end = watch.elapsedTime();
          System.out.println("linear time insertion took " + (end - start) + "s");
          start = watch.elapsedTime();
          // O(n)
          for (int i = 0; i < nums.length; i++) {
              // constant time insertion into linkedlist
              linkedlist.add(0, i);
          }
          end = watch.elapsedTime();
          System.out.println("constant time insertion took " + (end - start) + "s");
      }
  }