Chapter 2

What specific approach to efficient algorithms should we take?

• Identify broad themes and design principles which we can apply to a variety of problems.\
• Learn to apply these themes and principles to actual problems that vary our implementations subtlety.
• We should learn the distinction between different combinatorial approaches as to improve efficiency whether it's storage, computational speed, etc.

What is an efficient algorithm?

• An algorithm is efficient if, when implemented, it runs quickly on real input instances.
• This definition misses some points though like where and how well we implement the algorithm, what a real input instance is, and how does it scale.

Worst-Case Running Times and Brute-Force Search

• Slowest possible run-time of an algorithm given size N.
• Useful because it's often hard to quantify the average-case scenario or input for an algorithm.
• To tell if a worst-case runtime is efficient, compare it to a brute-force method.
• Ex. brute forcing the stable matching algorithm is O(n!) while the worst-case scenario is only O(n^2).

New definition for efficient algorithm:

• An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search.

Polynomial Time Definition

• A “reasonable” running time is when an input * size is scaled by a constant factor, the algorithm will only slow down by a constant factor.
• An algorithm is efficient if it has a polynomial running time.
• While this is sometimes vague or fails for some extreme examples, it's better than the first two definitions.
• This definition is good because some questions just don't have efficient solutions while others do.

Runtime Bounds

• No need to get extremely specific in them as that is an exhaustive effort and unnecessary (unless you are under oppressively fine constraints for an algorithm's implementation).
• By using a certain level of vagueness, similarities between algorithms start to appear.

Asymptotic Upper Bounds

• An upper bound exists if the worst-case running time is less than a constant multiple of f(n).

Asymptotic Lower Bounds

• A lower bound exists if the best-case running time is more than a constant multiple of f(n) for a sufficiently large size N. (necessary to prove scaleability, not just for tiny insignificant cases).

Asymptotic Tight Bounds

• If we can show both an asymptotic upper and lower bound are the same as the run time then we can say we have found the right bounds.
• These tight bounds are good to find for worst-case runtime scenarios as they show the runtime precisely.

Properties of Asymptotic Growth Rates

• Transitivity: if a function F is upper bounded by another function H which itself is upper bounded by another function G then we can say that function F is is bounded by function G.
• Sums of Functions: if an upper bound applies to both function F and function G individually then it applies to the sum of the functions F and G.

Asymptotic Bounds for Some Common Functions

• Polynomials
  • If a polynomial is to degree D then the runtime is O(n^D).
  • A polynomial-time algorithm is one whose running time T(n) is O(n^D) for some constant D where D is independent of the input size.
• Logarithms
  • Logarithms are slow growing functions. No matter the base of the logarithm in O(log n), it won't change much.
• Exponentials
  • Exponentials have fast rates of growth.
  • For every r > 1 and every d > 0, we have n^d = O(r^n).
  • Don't just say a function is exponential (like people do with log).

Linear Time - O(n)

• A linear running time means that a function will grow at most at a constant rate times the input size (n).
• Computing the Maximum:
  • Computing the maximum number in a list can be done with a single pass through of the list. By holding the current max value in a variable, you just need to update it as necessary if you find a larger value as you iterate through the list.
• Merging Two Sorted Lists:
  • Have pointers directed to the head of each sorted list. Then just see which item is smaller and append that to the output list. Move the pointer from that list along to the next item and repeat this process until one list is empty. Then append the rest of the other list to the output list and voila.

O(n logn) Time

• O(n logn) is the running time of any algorithm that splits its input into two equal halves, solves each piece recursively, and then combines the two solutions in linear time.
• Sorting (ex. merge sort) is the best known example of this problem.
  • Merge sort works by splitting the input into two equally-sized halves. The two halves are then sorted recursively and then merged into a single sorted output list.

Quadratic Time - O(n²)

• An example of quadratic running time is finding the smallest distance between two points on an n x n grid.
  • First you can compute every single pair of points possible (x,y) by iterating two for loops of n.
  • Then you can compute the distance by using the constant run time distance formula (no need to write it out). If the distance is smaller than the minimum value you already have, replace it.
  • Return the minimum when the the for loops are over.

Cubic Time - O(n³)

• An example of cubic running time is when you have multiple sets which are each subsets of set n. You want to check if the sets are disjointed (have no elements in common)
  • For set S1:
    • For set S2:
      • For each item in S1:
        • Determine if the item is also in S2
• Each set can only be O(n) so the three for loops results in O(n³).

O(n^k) Time

• An example of when O(n^k) running time occurs is anytime you search over all subsets of size k (ex. finding independent sets in a graph).
• For some k, find if there exists a any independent sets in graph G.
  • Enumerate all subsets of k nodes - this will run in O(n^k)
  • Check if any edge in each subset S joins two subsets together. - this will run in constant time for each subset so it won't be included in the overall running time
  • No edges joining a subset to any other subset means it's an independent graph.

Beyond Polynomial Time

• There are countless other common running times that you will come across. These include things like O(2ⁿ) and O(n!).
• O(2ⁿ) Time
  • Arises naturally as a running time for a search algorithm that must consider all subsets.
• O(n!) Time
  • Grows more rapidly than O(2ⁿ) time.
  • Arises for two reasons often:
    • n! is the number of ways to match up n items with n other items (ex. brute force stable matching problem).
    • n! is the number of ways to arrange n items in order (ex. traveling salesman problem).

Sublinear Time

• While it only happens rarely, running times can be asymptotically smaller than linear.
• This usually occurs when input can be “queried” indirectly instead of having to just read an input (ex. binary search).
• Binary Search - O(logn)
  • By nature binary search only works on sorted arrays so we can take advantage of that and try halfway points in the array until we are able to pinpoint the item.
  • This removes half of the array that you are searching effectively with each recursive step that happens.
  • The O(logn) run time only applies when it takes a constant amount of work to remove half the input each time from the search.

The Problem

• Priority queues are designed for applications in which elements have a priority value (or key) and we want to select an element which has the highest priority.
• Smaller keys represents higher priorities.
• Useful for situations which manage real-time events (ex. scheduling processes on a computer).
• Running time:
  • Adding = O(logn)
  • Removing = O(logn)
  • Selecting = O(logn)
  • Sorting = O(n logn)

Implementation of a Priority Queue (Heap)

• Heaps are like balanced binary trees with a root and each node having potentially one left and one right child.
• Keys (items) are in heap order if the key is equal or larger than its parent node in the tree (keys grow as you go down the tree essentially).
• The heap will be stored in an array rather than using pointers:
  • Root = first item in the list
  • Left child(i) = List[2i]
  • Right child(i) = List[2i + 1]
  • Parent(i) = List[i/2]
• Operation Running Times:
  • StartHeap(n) = O(n)
    • returns initialized empty heap H in the form of an array hence the linear running time.
  • FindMin(H) = O(1)
    • returns the first item in the array which is the smallest key in the heap.
  • Insert(H, v) = O(logn)
    • Uses “Heapify-Up” algorithm to add item (v) to the heap (H) and rectifies the potentially broken heap.
  • Delete(H, i) = O(logn)
    • Uses either “Heapify-Up” (replacement key (i) is too small for position it's filling) or “Heapify-Down” (replacement key (i) is too large for position it's filling).
  • ExtractMin(H) = O(logn)
    • Deletes the minimum key value in the heap which uses both FindMin(H) and Delete(H,i) hence the O(logn) running time.
  • By maintaining a separate position array we can also:
    • Delete(H, Position[v]) = O(logn)
    • ChangeKey(H, v, a) = O(logn)
• Heapify-Up
  • Push the too small key upwards in the tree by switching it with its parent node.
  • Run Heapify-Up on the parent now (on itself again effectively).
• Heapify-Down
  • Push the too large key downwards in the tree by switching it with one of its children nodes.
  • Run Heapify-Down on the child node now that the too large key switched with. (on itself again effectively).