Time Complexity

Implementing Sparse Array w/ Search Structure

In terms of implementing a sparse array with a search structure, you can implement any search strcuture as you wish (a search structure must be able have a find function which returns a boolean value. That will indicate whether the item is found or not).

For example, you can implement a sparse array with memos. With these memos, you have pairs (i, A[i]) where i is the query and A[i] is the collection of items/data of said query.

Complex Numbers

Modulus of $e^{cos\theta + isin\theta}$ is simply just ${\sqrt{cos^2{\theta} + sin^2{\theta}}} = 1$

MUST REMEMBER THIS FORMULA: $\sqrt{a + bi} = \pm \sqrt{\frac{\sqrt{a^2 + b^2} + a}{2}} + \sqrt{\frac{\sqrt{a^2 + b^2} - a}{2}}$ if b > 0

$a^2 + b^2 = 1$ where $a = \frac{1}{\sqrt{2}}$ and $b = \frac{1}{\sqrt{2}}$

Runtimes of Algorithms Covered in this Class

Greedy Algorithms

Greedy Algorithms are considered “greedy” since you choose the best choices (lowest values) and combine them.

  1. Kruskal’s
  • Best Case:
  • Worst Case:
  • Average Case:
  1. Huffman Encoding
  • Best Case:
  • Worst Case:
  • Average Case:
  1. Prim’s algorithm
  • Best Case:
  • Worst Case:
  • Average Case:

Graph Algorithms

Dynamic Programming

Uses/relies on memoization to boost performance/shorten runtime complexity of an existing algorithm.

  1. Floyd-Warshall
  • Best Case:
  • Worst Case:
  • Average Case:
  1. Bellman-Ford
  • Best Case:
  • Worst Case:
  • Average Case:

Divide and Conquer

  1. Mergesort (Sorting Algorithm)
  • Best Case: $\Omega(nlogn)$
  • Worst Case: $O(n logn)$
  • Average Case: $\theta(nlogn)$
  1. Quicksort (Sorting Algorithm)
  • Best Case: $\Omega(n logn)$
  • Worst Case: $O(n^2)$
  • Average Case: $\theta(n logn)$
  1. Binary Search (Selection Algorithm)
  • Best Case: $O(1)$
  • Worst Case: $O(logn)$
  • Average Case: $O(logn)$

Hash Tables

Closed Hasing

Open Hashing

Treaps

Is a combination of both a tree and a heap.

Must be able to know how to calculate the modulus of the e^theta(i) problem. Again, look at the last page of the 3rd midterm.

Last Problem of 3rd Midterm: Runtime When Implementing Memos

               f(n)
            /   |    \
        f(n/2)  |    f(n/3)
       /  |  \  |  /    |    \
   f(n/4)    f(n/6) f(n/18) f(n/9)
  /      \

In terms of implementing a memos for a recursive functions, when you use a treap, the runtime would be $\theta(log^2nloglogn)$