Table of Contents

Introduction

• An abstract data type is the interface of a data structure. They group data structures by category, but have no implementation.
  • List (ADT, no implementation)
    • ArrayList (implementation 1)
    • Linked List (2)

Complexity Analysis

• Time complexity measures how much a program’s runtime slows down for very large data sets.
  • Runtime vs size of input data (N)
• Space complexity measures how much a program’s memory usage increases for very large data sets.
  • Space usage vs size of input data (N)

Time Complexity

• Inefficient algorithms slow down by a lot for larger input data (exponential), but are still fast for small inputs.
• Usually, you want to know the worst-case time complexity of the algorithm you use, but also be aware of cases where the amortized time complexity is faster.

Big Oh

• This is the primary way of measuring the time and space complexity of algorithms.
• f(n) = O(g(n))
  • f(n) is the growth function
  • g(n) is a function used to represent the growth function.
    • Equal or higher order
    • No constants
    • No lower orders.
• Example
  • f(n) = 5n^2 + 3n + 6 = O(N^2) = O(N^5) (not a tight bound, but valid)
• Try to keep the bound as tight as possible.
• Big Oh utilizes
  • Worst-case analysis
    • This is a method of recording runtime data to find an algorithm’s growth function.
    • When running the algorithm on a data set of a particular size, N, what kind of dataset causes the worst possible case of the runtime to occur? In other words, what kind of dataset does the algorithm take longest to work on?
    • Test the algorithm on many “worst-case” datasets of different sizes. Plot all the data points on a curve of runtime vs size N. This is your algorithm’s growth function.
    • Example: Array searching
      • You have an array of size 5. You search through the array for a certain value.
      • Worst-case scenario: The value you’re searching for is at the end of the array. You have to loop through every other element before you find it and finish the search.
      • Record the runtime for searching an array of size 5, with the target element at the end of the array.
      • Repeat for many different array sizes. Record the runtimes for each N
      • Plot them. This is the growth function of searching an array, using worst-case analysis.
  • Upper bound
    • This is a method of simplifying the growth function into a smooth curve and short math expression.
    • Simplifying the curve: Draw a new curve as an upper bound of the growth function.
      • Each point on the curve shows the maximum time the algorithm may take to execute for input size N.
    • Simplifying the function:
      • Eliminate all but the highest order. Eliminate constants.
      • Any function that’s equal or higher order satisfies Big Oh.
• Alternatives to worst-case analysis.
  • Average-case: Plots the average runtime for a dataset of each dataset size N.
    1. Find the algorithm’s runtime on all possible datasets of a particular size, ex N=5.
    2. Calculate the average of every case. Plot it.
    3. Repeat for many differently sized datasets to find your growth function.
  • Expected-case: Combines average-case with probabilities to plot the expected value of runtime of each dataset size N.
    1. Find the algorithm’s runtime on all possible datasets of a particular size N.
    2. Multiply each case by the probability of it occurring.
    3. Add them up to find the expected value of the runtime for size N. Plot it.
    4. Repeat for many different sizes to find your growth function.

Amortized Analysis

• This is a special case of calculating the worst-case time complexity of an algorithm.
• It accounts for algorithms where the worst-case happens very rarely, and the usual runtime is much faster than that.
  • Example: inserting into a dynamic array.
    • O(1) if the array isn’t empty.
    • O(N) when the array is full. You have to create a new array, copy every element over, and then insert the new element.
    • This rarely happens, so the amortized time complexity is O(1)