//O(n) for (int i = 0; i < n; i++) { } for (int i = 5; i < n; i++) { }
//O(n) for (int i = 5; i < n; i+=7) { }
for i <- 1to sqrt(n)//O(sqrt(n)) for i <- sqrt(n) to n //O(n) for i <- n to n/2//O(n)
for i <- n to n step n/2//O(1)
1 < logn < sqrt(n) < n < n^2
for (int i = 1; i < n; i *= 3) { } //O(logn) for (int i = 1; i < n; i = i * 3 + 8) { }//O(logn) for (int i = 1; i < n; i *= 2) { // 1, 2, 4, 8, …. log2(n) } for (int i = 1; i < n; i *= 3) { // 1, 3, 9, 27, …. log3(n) } for (int i = 1; i < sqrt(n); i *= 3 {} //O(log sqrt(n))
//O(n*n) = O(n^2) for (int i = 0; i < n; i++) //O(n) for (int j = 0; j < n; j++) { //O(n) } }
//O(n+n) = O(n) for (int i = 0; i < n; i++) //O(n) } for (int j = 0; j < n; j++) { //O(n) }
//sum(1...n)=O(n^2) for (int i = 0; i <= n; i++) //O(n) for (int j = 0; j <= i; j++) { // 1 + 2 + 3 + … + n-1 + n } }
//O(n*sqrt(n)) for (int i = 0; i <= n; i++) { //O(n) for (int j = 0; j < sqrt(n); j++) { //O(sqrt(n)) } }
for (int i = 0; i <= n; i++) { //O(n) for (int j = 0; j < n-sqrt(n); j++) { } }
//O(n log2n) for (int i = 0; i < n; i++) { // O(n) for (int j = 1; j < n; j *= 2) { // O(log2n) } }
//n(1+1/2+1/4+1/8+...) //\sum(1/2^i)=1 //O(n) for (int i = 1; i <= n; i *= 2) { // O(log2n) for (int j = 1; j < i; j++) { // O(1 + 2 + 4 + 8 + …. + n) } }
//O(n+m) if n ≈ m O(2n) = O(n) for (int i = 0; i < n; i++) { //O(n) } for (int j = 0; j < m; j++) { //O(m) cout << i * j; //O(1) }
for (int i = 1; i < n; i *= 2) //O(log n) for (int j = 1; j < n; j++) //O(n) System.out.println(i*j);
for (int j = 1; j < n; j++) //O(n) for (int i = 1; i < n; i *= 2) //O(log n) System.out.println(i*j);
for (int i = 0; i < n; i++) //O(n) for (int j = i; j < n; j++) // n + (n-1) + (n-2) + … 1 print(“x”);
sum ← 912851; //O(1) for i ← 1 to n for j← 3 to i // 0 + 0 + 1 + 2 + 3 + … n-3 = O(n^2) sum ← sum + i*j; end end
int f(int n) { if (n <= 0)//O(1) return1; return n * f(n-1); } f(5)=5*f(4)=5*4*f(3)...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
//Fibo intfibo(int n){ //O(n) int a = 1, b = 1, c; for (int i = 0; i < n; i++) { c = a + b; a = b; b = c; } return c; }
voidselectionSort(int x[], int n){ //O(n2) for (int j = n - 1; j > 0; j--) { int pos = 0; for (int i = 1; i <= j; i++) { if (x[i] > x[pos]) pos = i; } if (j != pos) swap(x[pos], x[j]); } }
Insertion Sort
1 2 3 4 5 6 7 8 9 10 11 12 13 14
voidInsertionSort(int x[], int n){ for (int i = 1; i < n; i++) { int temp = x[i]; for (int j = i - 1; j >= 0; j--) if (x[j] > temp) x[j+1] = x[j]; else { x[j+1] = temp; break; } } x[0] = temp; //TODO: BAD edge case here } }
quicksort(int[] x, int left, int right) { if (right - left < 2) return; int pivot = (x[left] + x[right])/2; int i = left, j = right; while (i < j) { //O(n) while (x[i] < pivot) i++; while (x[j] >= pivot) j--; if (i < j) { swap(x[i], x[j]); } } //i == j quicksort(x, left, i-1 ); // logn quicksort(x, i, right); }
makeheap(x) for i ← n/2 to 0 makesubheap(x, i) end
makesubheap(x, i) if x[2i+1] > x[2i+2] if x[i] < x[2i+1] swap(x[i], x[2i+1]) makesubheap(x, 2i+1) end else if x[i] < x[2i+2] swap(x[i], x[2i+2]) makesubheap(x, 2i+2) end end
heapsort(x) makeheap(x) for i ← n-1 to 1 swap(x[0], x[i]) makesubheap(x, i-1) end end //makeheap = (n/2-1) log n + rebuild heap (n-1) log n = O(n log n)
Merge Sort
work each time: n
number of iterations log n
O(n log n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// merge lists a,b of size n into list c of size 2n merge(a, b, c) { i ← 0// position in a j ← 0// position in b k ← 0// position in c while i < n and j < n if a[i] < b[j] c[k] ← a[i] i ← i + 1 else c[k] ← b[j] j ← j + 1 end k ← k + 1 end }
Shuffling
1 2 3 4 5 6
Fisher-Yates(x) // O(N) for i← x.length-1 to 0 pick ← random(0, i) swap(x[i], x[pick]) end end
Searching
Linear Search
search(x, target)
$O(n),\Omega(1), avg = n/2$
Binary Search
sort:O(n log n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
binarySearch(x, target) L ← 0 R ← x.length-1 while (L < R) mid ← (L + R) / 2 if x[mid] > target R ← mid - 1 elseif x[mid] < target L ← mid + 1 else return mid end return NOTFOUND end
Golden Mean Search
L = 0
R = 19
S = (R-L) / = 19 * .6 = 11.4 =
function f(x) = 4 - x2
L = -2 R = 1 D = R-L = 3
S = (R-L)/ 1.618 = 1.85
X = R - 1.85 = -.85
Y = L + 1.85 = -.15
L = -.85
S =(R-L)/ 1.618 = 1.143
X = -.15
Y = L + S = -.85 + 1.143 = .293
R = .293
Number Theoretic Algorithms
gcd
1 2 3 4 5 6
gcd(a,b) if b == 0 return a end return gcd(b, a mod b) end
$O(logn),\Omega(1)$
lcm
1 2
//O(log n) lcm(a,b) = a * b / gcd(a,b) // 1 + log(n)
//raise x to the power n bruteforcepower(x, n) prod ← 1 for x ← 1 to n prod ← prod * x end return prod end
//O(log n) //raise x to the power n power(x, n) prod ← 1 while n > 0 if (n mod 2 != 0) prod ← prod * x end x ← x * x n ← n / 2 end return prod end
//xn mod m powermod(x, n, m) prod ← 1 while n > 0 if (n mod 2 != 0) prod ← prod * x mod m end x ← x * x mod m n ← n / 2 end return prod end
Fermat
if a^p-1 mod p == 1⇒ p is probably prime
if a^p-1 mod p != 1⇒ p is definitely NOT prime
Miller-Rabin
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
MillerRabin(n, k) WitnessLoop: for i ← 1 to k // k trials a← random[2, n − 2] x ← a^d mod n if x = 1or x = n − 1 then continue WitnessLoop for j ← 1 to s − 1 x ← x2 mod n if x = 1 then returnfalse composite (Carmichael?) if x = n − 1 then continue WitnessLoop end returnfalse (composite) return probably prime
brute force trial division
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
//O(n) Ω(1) bool isPrime(int n) { for (int i = 2; i < n/2; i++) { if (n % i == 0) return false; } return true; }
//O(√n) Ω(1) bool isPrime(int n) { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; }
Eratosthenes’ Sieve
1 2 3 4 5 6 7 8 9 10 11 12 13 14
ImprovedEratosthenes(n) for i ← 2 to n isPrime[i] ← true end for i ← 4 to n step 2 isPrime[i] ← false end for i ← 3 to n step 2 if isPrime[i] for j ← i*i to n step 2i isPrime[j] ← false end end end
add(k) if 2*used >= capacity grow() pos ← hash(k) while table[pos] != EMPTY pos++ if pos >= table.length pos = 0 end end used++ table[pos] ← k end
find(k) pos ← hash(k) while table[pos] != EMPTY if table[pos] == k return true end pos++ if pos >= table.length pos = 0 end end return false end
bool ← remove(k) pos ← hash(k) while table[pos] != 0 if table[pos] == k table[pos] ← 0 // redo everyone potential // until next 0 return end pos++ if pos >= table.length pos = 0 end end return false end
addition(a, b) if a.rows != b.rows OR a.cols != b.cols ERROR end for i ← 0 to rows*cols ans[i] = a[i] + b[i] end return ans end
Multiplication
1 2 3 4 5 6 7 8 9 10 11 12 13 14
mult(a, b) if a.cols != b.rows ERROR end for k ← 0 to a.rows-1 for i ← 0 to b.cols - 1 sum ← 0 for j ← 0 to a.cols - 1 sum ← sum + a(k,j)*b(j,i) end ans(k,i) ← sum end end end
Solving systems (Gauss-Jordan Elimination, partial pivoting)
partialPivot(A,i) max ← A(i,i) maxpos ← i for j ← i+1 to rows-1 if A(j,i) > max max ← A(j,i) maxpos ← j end end //swap rows GaussianElimination(A,i) for i ← 0 to rows-2 partialPivot(A,i) for j ← i+1 to rows-1 s ← - A(j,i)/A(i,i) A(j,i) ← 0 for k ← i+1 to cols - 1 A(j,k) += s * m(i,j) end end end
voidboyerMoore(constchar s[], constchar target[]){ int jump[256]; int n = strlen(s); int len = strlen(target); for (int i = 0; i < 256; i++) jump[i] = len; for (int i = 0; i < len; i++) jump[target[i]] = len - 1 - i; for (int i = len - 1; i<n;){ int offset = jump[s[i]]; if(offset > 0) i += offset; else{ for (int j = i - len +1, k = 0; j < i; j++, k++) if(target[k] != s[j]) goto notfound; cout << "Found:" < i-len +1<<endl; notfound: i+=len; } } for i =0 to 255 table[i] = len for i = 0 to len table[target[i]] = len - i - 1 i = len-1 while (i < n) jump ← table[search[i]] if (jump == 0) { // possible match // compare the word letter by letter
classFiniteStateMachine { private: int currentState; int next[NUMSTATES][256]; public: FiniteStateMachine() : currentState(0) { for (int i = 0; i < 256; i++) next[0][i] = 1; for (int i = 'a'; i <= 'z'; i++) next[0][i] = 0; for (int i = 'A'; i <= 'Z'; i++) next[0][i] = 0;
} voidexec(constchar inp[]){ for (int i = 0; inp[i] != '\0'; i++) { currentState = next[currentState][inp[i]]; if (currentState == 1) return; // get out when we reach the end state } };
LCS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
intLCS(string s, string t){ int m = s.size(); int n = t.size(); int dp[m+1][n+1]; for(int i = 0; i < m + 1; i++){ for(int j = 0; j < n + 1; j++){ if(i==0||j==0){ d[i][j]=0; } elseif(s[i-1]==t[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; }else{ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } } return dp[m][n]; }
Graphs
Representation: list or matrix
find out if v1 is adjacent to v2 = O(E) = O($V^2$) Ω(1)
find out the set of vertices connected to v is O(E)
g.DFS2(v,visited) //O(V^2) Ω(1) with list impl visited[v] ← true print v foreach v2 in adjacent(v)// for matrix O(v), for linkedlist O(v) Ω(1) if NOT visited[v2] g.DFS2(v2, visited) end end end g.DFS(v) visited ← [false, false, ...,] //O(v) g.DFS2(v,visited) end
//iteratively g.DFS(v) visited ← [false, false, ...,] //O(v) stack ← empty stack.push(v) visited[v] ← true while NOT stack.empty() v ← stack.pop(); print v foreach v2 in adjacent(v) if NOT visited[v2] stack.push(v2) visited[v2] ← true end end end end
BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
g.BFS(v) visited ← [false, false, ...,] //O(v) queue ← empty queue.enqueue(v) visited[v] ← true while NOT queue.empty() v ← queue.dequeue(); print v foreach v2 in adjacent(v) if NOT visited[v2] queue.enqueue(v2) visited[v2] ← true end end end end
IsConnected
1 2 3 4 5 6 7 8
bool ← g.isConnected() //O(V^2) visited ← g.DFS(r) for i ← 0 to V if NOT visited[i] return false end return true end
Bellman-Ford//O(VE)
1 2 3 4 5 6 7 8 9 10 11
BellmanFord(start, end) cost ← [∞, ∞, ...] cost[start] ← 0 for v ← 0 to V-1 for each edge e from v if cost[v2] > cost[v] + adjacent[v2] cost[v2] ← cost[v] + adjacent[v2] add to the list to recompute costs from v2 end end end
Floyd-Warshall//O(V^3)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
dist ← |V| × |V| array of minimum distances initialized to ∞
for each vertex v dist[v][v] ← 0 for each edge (u,v) dist[u][v] ← w(u,v) //the weight of the edge (u,v) for k from 1 to V for i from 1 to V for j from 1 to V if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end end end end
Prim//O(V^2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Prim(v) visited ← new Vector(V, false) visited[v] ← true for i ← 1 to V-1 for all edges out of the visited set(V,2V,3V, ...) to V-1 min ← ∞ if isAdjacent(v,a) and NOT visited[a] if getWeight(v,a) < min min ← getWeight(v,a) minA ← a end end end visited[minA] ← trme v ← minA end end