Prerequisites

Best: O(nlog(n))

Average: O(nlog(n))

Worst: O(n^2)

Best: O(n^2)

Average: O(n^2)

Worst: O(n^2)

Best: O(n)

Average: O(n^2)

Worst: O(n^2)

Best: O(n)

Average: O(n^2)

Worst: O(n^2)

Best: O(nlog(n))

Average: O(nlog(n))

Worst: O(nlog(n))

Best: O(nlog(n))

Average: O(nlog(n))

Worst: O(nlog(n))

Balanced Tree

query: O(logn)

build: O(n)

Examples: AVL-tree, Red-Black tree

Unbalanced Tree

query: O(n)

build: O(n)

problem is NP and all other NP problems are polynomial-time reducible to it

Basic Strategy to prove Problem X is NP-complete

1. Prove X ∈ NP

2. Choose a problem Y that is known to be NP-complete

3. Prove that Y ≤p X

Bubble Sort, Insertion Sort, Merge Sort, Count Sort

Quick Sort, Heap Sort, Selection Sort

Best: O(n+k)

Average: O(n+k)

Worst: O(n+k)

uses count sort

O(d(n+k))

O(1)<O(logn)<O(sqrt(n))<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)

Upper bound

O(g(n)) = f(n) there exists a positive constant c and no such that 0 ≤ f(n) ≤ cg(n) for all n ≥ no

Lower bound

Ω(g(n)) = f(n) there exists positive constant c and no such that 

0 ≤ cg(n) ≤ f(n) for all n ≥ no

Tight bound

Θ(g(n)) = f(n) there exists positive constants C1 and C2 and no such that 0 ≤ C1g(n) ≤ f(n) ≤ C2g(n) for all n ≥ no

O(V+E)

LIFO

FIFO

Heapify: O(logn)

Build Heap with Heapify: O(n)

Find Max/Min: O(1)

Extract Max/Min: O(logn)

Increase Key: O(logn)

Insert: O(logn)

Delete: O(logn)

Merge: O(n+m)

Find Max/Min: O(logn)

Extract Max/Min: O(logn)

Increase Key: O(logn)

Insert: O(logn)

Delete: O(logn)

Merge: O(logn)

Find Max/Min: O(1)

Extract Max/Min: O(logn)

Increase Key: O(1)

Insert: O(logn)

Delete: O(logn)

Merge: O(1)

• Proof by contradiction

• Proof by induction (stay ahead)

• Proof by exchange

1

0

• not optimal for finding the shortest path

• used in various applications such as acyclic graphs and topological order etc.

• recursive algorithm that uses the idea of backtracking

edge (x,y) in DFS means: x or y is the ancestor of the otger

• optimal for finding the shortest path

• used in various applications such as bipartite graphs, shortest paths, etc.

• no concept of backtracking

edge (x,y) in BFS means: x and y differs by at most 1 layer

• Show that sequence of n operations takes worst time T(n)

• In the worst-case average cost is T(n)/n

O(ElogV) using min priority queue (binary heap)

Fibonacci Heap: O(E+VlogV)

Kruskal time:O(E * logE)

space: O(V+E)

Prim: O(V^2) (can be O(E * logV) with the help of a binary heap)

space: O(V)

Ford-Fulkerson

runtime:O(|E| * f), where |E| is the number of edges and 'f' is the maximum flow of a network

Edmond-Karp: runtime: O(|V| * E^2)

space for both: O(V)

runtime: O(n+m)

Suffix Trie

• create: O(m^2)

• space: Ω(m^2)

• search for pattern: O(n)

Suffix Tree

• create: O(m) (McCreights)

• space: O(2n − 1) 

  • n is number of leaves

• search for pattern: O(n)

• transformation: O(n) (use skew algorithm)

• decoding: O(n)

• query: O(n)

O(km+|C|n)

k=amount of mismatches that are allowed

|C|= number of candidates