COMP 252

Big O

Upper Bound

Uppercase Omega

Lower Bound

Uppercase Theta

Asymptotic Behavior

Little O

limit approaches 0

Lowercase Omega

limit approches infinity

Constant Time

O(1)

Logarithmic Time

O(log n)

Linearithmic Time

O(n log n)

Linear Time

O(n)

Quadratic Time

O(n²)

Exponential Time

O(2^n)

Factorial Time

O(n!)

Tower Functions

O(2²^n)

Recursive Fibonacci Time Complexity

O((1+sqrt(5)/2)^n)

Dynamic Fibonacci Time Complexity

O(n)

Fast Exponentiation Fibonacci Time Complexity

O(log n)

Chip Testing Algorithm

Even: Pair all and eliminate non GG pairs until there is 1. Odd: take a vote of n-1 chips and declare good if tie

Chip Testing Complexity

O(n)

Karatsuba Algorithm

Bit multiplication because a1*b2+a2*b1 = (a1-a2)(b2-b2)+ab1+a2b2

Karatsuba Time Complexity

O(n^log_2 3) = n^1.58

Toom Cook Improvement (Toom3)

Divides a and b into 3 parts

Toom3 Complexity

O(n^log_3 5) = n^1.46

Merge Sort Complexity

O(n log n)

Convex Hull Complexity

O(n log n)

Reccurance by Induction

1. Guess 2. State Hypothesis T(k) ,+ c* … for k < n 3. Substitute to reccurance 4. Simplify to exact form 5. Prove the base case

Binary Search Complexity

O(log n)

Master Theorem Form

T = a Tn/b + f(n)

Master Theorem Case 1

n^log_b a / f(n) > n^epsilon → O(n log_b a)

Master Theorem Case 2

f(n) / n^log_b a > n^epsilon → O(f(n)

Master Theorem Case 3

f(n) = O(n^log_b a) → O(n^log_b a log_b n)

Recursion Tree

1. identify components: a subproblems n/b size of subproblem f(n) cost outside recursion

2. draw root with f(n)

3. draw a branches and f(n/b) to each child node

4. calculate cost per level (sum)

5. determine depth until sub problem is 1, log b n

6. calculate cost of leaves n

7. sum total cost

Strassen Time Complexity

O(n^log_2 7) = n².807

Euclids Algorithm

GCD(n,m) = if m==0 return m =0 else return GCD(m, n mod m)

Euclids Algorithm Complexity

O(log n log m)

Half Space Counting Problem Algorithm

if |S| <= 10 do it manually else determine 3 set cut by l if the fourth set is on the good side of l return |S|/4 + Count(l, A) + Count(l, B) + Count(l, C) else return Count(l, A) + Count(l, B), + Count(l, C)

Half Space Counting Problem Complexity

O(n^log_4 3)

Kth Smallest Element (Kth order statistic) Algorithm

Select(k, S) = if |S| <= 5, Sort(S) return kth smallest element else group all elements in groups of 5, find their medians and call the set M. Let m = select(|M|, 2, M) the median of medians. Compare all elements of S with m to form L and R. if |L| == k-1 return m, else if |L| >= k return Select(k, L) else return Select(k-|L| -1, R)

Kth Smallest Element Complexity

O(n log n)

Binomial Coefficient Algorithm

for n= 0 to N for k= 0 to k if k=0 or k=n then n choose k = 1 else n choose k = n-1 choose k-1 + n-1 choose k

Binomial Coefficient Complexity

O(N*K)

Sterling Number Algorithm

Same as Binomial Coefficient but initialize with 1 and use property P(n,k) = k*P(n-1, k) + P(n-1, k-1)

Travelling Salesman Problem (TSP) Algorithm

Length Between 1 and j via all S: for all j not in 1, L[1, empty, j] = dist[1,j]. for all S with |S| = k, S subset {2, … n} for all j not in S. L[1,S,j] = min in S (L[1, S-{k},l]+dist[l,j])
TSPLen= min (L[1,S,j] + dist[1, j])

TSP Time Complexity

O(n²2^n)

Knapsack Problem Algorithm

1. for n = 0 to N

2. for k= 0 to K

3. if n = k= 0 then P[n, k] = 1

4. else if n = 0, k > 0 then P[0, k] = 0 // no elements

5. else if n > 0, k= 0 then P[n, 0] = 1 // can choose the

// empty set S to fill a knapsack of capacity 0

6. else P[n, k] =

P[n- 1, k] if xn > k (no solution)

1 if xn = k (definetely solution)

max(P[n-1, k], P[n-1, k-xn]) if xn < k (put it in or don’t put it in)

Knapsack Problem Complexity

O(NK)

Assignment Problem Algorithm

for k = 0 to n for all sets A and B subsets of 1 to n with |A| = |B| = k: if k= 0 then Best(empty, empty) = 0
else Best[A,B] = max( delta xy + Best[A-{X} , B-{y}])

Assignment Problem Complexity

O(n²4^n)

Job Scheduling Algorithm

for k = 0 to N for all subsets S in 1 to n of size k do C(s) = min (cost of all jobs without job i+ cost of job i)

Job Scheduling Complexity

O(n2^n)

Longest Common Subsequence Algorithm

for all i = 0 to n for j = 0 to m if i = 0 or j = 0 then L[i, j] = 0 else L[i,j] = 1+L[i-1,j-1] if xi = xj, max(L[i-1,j], L[i,j-1]) if xi not xj
THEN start at cell of last row of last column, repeat until out of bounds. if xi = yj append xi to r and go northwest else if xi not yj choose max between numbers in the west and north cells

Optimal Binary Search Tree Algorithm

if you have a range of keys from k_i to k_j, and you pick k_r to be the root:

1. The Left Subtree must be an optimal BST for keys k_i to k_{r-1}

2. The Right Subtree must be an optimal BST for keys k_{r+1} to k_j

So compute W[i,j] sum of frequencies for all keys between index i and j
Then compute C[i,k]: try every possible key as the root and take cost of left and right subtrees and add the penalty for those subtrees being pushed down a level.

Matrix Multiplication

Calculate the cost for all chains of length 2, then all chains of length 3 (using results from 2) until finds cost for full length n

Worst Case Time Complexity of an Algorithm

T(A, x1.. xn) = Tn(A) = max x1 to xn T(A; x1, … xn)

Lower bound complexity of a problem

min A Tn(A)

Decision Tree Bound

min A Tn (A) >= log k L (k-ary tree with L leaves)

Lower Bound to Report all Numbers

n

Lower Bound to Search for X (sucessful)

ceil (log n)

Lower Bound to search for X (unsuccessful)

ciel(log n+1)

Lower Bound to search for x (general)

ceil (log 2n + 1)

Lower Bound to Sort

ciel (log n!)

Adversary Method

Construct Bad Input to make algorithm as slow as possible

Free Tree

Connected Acyclic Graph

Rooted Tree

Free Tree with a Single Marked Node called Root

Ordered Rooted Tree (Plane Tree)

A rooted tree with each subtree given an order

k-ary Tree

Each node has exactly k subtrees

Complete Binary Tree

All Levels are filled with the exception of the last one which is filled left to right

Height of a Complete Binary Tree

floor ( log_2 n)

Bijection to Binary Tree

1. map root to root of binary tree

2. take the older child and make it the left child

3. take siblings and make it the right child of new binary node

4. apply recursively

Complete Binary Tree Linear

i at [i], left child at [2i], right child at [2i+1]

Edges of a tree on n nodes

n-1 edges

Number of leaf nodes n0 is exactly one more than the number of nodes with 2 children

n0 = n2 + 1

Number of binary trees on n nodes is given by nth catalan number

1/n+1 × 2n choose n

Level Order Traversal Algorithm

Visit level by level

Preorder Traversal Algorithm

Visit Root, Visit Left, Visit Right

Inorder Traversal Algorithm

Visit Left, Visit root, Visit Right

Postorder Traversal Algorithm

Visit Left, Visit Right, Visit Root

Encoding of a binary tree

no children 00, left child 10, right child 01, both children 11

Expression Tree Postfix Evaluation

read from left to right, if x is an operand put it on the stack, otherwise pop 2, evaluate with expression and push result to stack. return final item on stack

Dictionary Operations

Search, Insert and Delete, sometimes max/min and successor/predecessor

Main Dictionary Implementations

BST, Balanced Trees, Hash Tables, B-Trees, Tries and Suffix Trees

Entropy Scale

Amount of Effort it takes to create the data structure from an unordered list

Time complexity to traverse a tree

O(n)

Search Operation BST

if key is nil or the one we’re looking for return the key, else compare value and search left/right accordingly

Insert Operation BST

position at right node in BST and create a new cell with value at that position

Delete Operation BST

if x has no children then just update pointer, if only one child bypass node, if x has at most 1 child and is root, set child as new root, if x has 2 children take rightmost node in left subtree and transfer the key to x. then delete the rightmost node in the left most subtree

Cost of browsing in BST

O(h+k)

Red Black Tree Properties

External Nodes has no keys, are black and have rank o, node is black with rank r if its parent has rank r+1, node is red with rank r if its parent has rank r, if a node is red, none of its children or parent can be red

2-3-4 Tree View

Draw external nodes at sea level and draw red black trees with all black nodes of the same rank at the same level and red nodes between the levels

number of internal nodes in a red black tree and rank of root

r <= log_2 (n+1) <= 2r

height of red black tree

h M= 2*rank of root <= 2*log_2 (n+1)

Insert for RBT

Standard insert then fix

Delete for RBT

Standard delete then fix

Lazy Delete

Mark as deleted then rebuild when 50% are deleted by doing in order traversal and rebuilding the tree

Building a Red Black tree from sorted list Time complexity

O(n)

Building a Red Black tree from sorted list

Make a complete binary tree and make bottom level red

Insert/Delete/Search RBT Time Complexity

O(log n)

Fix Operation RBT

1. If parent and uncle are red: increase rank of grandparent, make grandparent red and make its children black, if at root stop

1. if parent is root and sibling red, change both children to black and stop

2. if parent is black, stop

3. if parent red and uncle black, preform rotation and stop

Right Rotate RBT

AxByC → AxyBC

Left Rotate RBT

AxyBC → AxByC

Join Operation RBT

1. Find smallest node j in B and run fix on B

2. Find same rank as root of B on right roof of A, a with parent b

3. set j rank to r+1 and make it red

4. attach subtree at a as the left child

5. attach root of B as right child

6. make j new child of of b

7. fix