Formulas

Computer Science

Complexity Analysis

Constant Time Complexity
O(1)
O(1) Algorithm Runtime Is Constant Regardless of Input Size

Linear Time Complexity
O(n)
O(n) Algorithm Runtime Grows Linearly with Input Size

Quadratic Time Complexity
O(n²)
O(n²) Algorithm Runtime Grows Quadratically with Input Size

Logarithmic Time Complexity
O(log n)
O(log n) Algorithm Runtime Grows Logarithmically with Input Size

Linearithmic Time Complexity
O(n log n)
O(n log n) Algorithm Runtime Grows Proportionally to n Times log n

Exponential Time Complexity
O(2ⁿ)
O(2ⁿ) Algorithm Runtime Doubles with Each Additional Input Element

Factorial Time Complexity
O(n!)
O(n!) Algorithm Runtime Grows Factorially with Input Size

Big O Notation
O(f(n))
O Upper Bound of Growth Rate
f(n) Function Describing Number of Operations
n Input Size

Big Omega Notation
Ω(f(n))
Ω Lower Bound of Growth Rate
f(n) Function Describing Number of Operations
n Input Size

Big Theta Notation
Θ(f(n))
Θ Tight Bound of Growth Rate
f(n) Function Describing Number of Operations
n Input Size

Amdahls Law
S = 1 / ((1 – p) + p/s)
S Overall Speedup
p Proportion of Program That Can Be Parallelized
s Speedup Factor of Parallel Part

Mathematical Foundations

Arithmetic Series Sum
S = n/2 × (a₁ + aₙ)
S Sum of the Series
n Number of Terms
a₁ First Term
aₙ Last Term

Geometric Series Sum
S = a₁ × (1 – rⁿ) / (1 – r)
S Sum of the Series
a₁ First Term
r Common Ratio
n Number of Terms

Infinite Geometric Series Sum
S = a₁ / (1 – r)
S Sum of the Infinite Series
a₁ First Term
r Common Ratio Where Absolute Value Less Than One

Fibonacci Sequence
F(n) = F(n-1) + F(n-2)
F(n) Nth Fibonacci Number
F(n-1) Previous Fibonacci Number
F(n-2) Fibonacci Number Two Positions Prior

Fibonacci Base Cases
F(0) = 0, F(1) = 1
F(0) Zeroth Fibonacci Number
F(1) First Fibonacci Number

Factorial Computation
n! = n × (n-1) × (n-2) × … × 1
n! Factorial of n
n Positive Integer

Binomial Coefficient
C(n, k) = n! / (k! × (n-k)!)
C(n, k) Number of K Combinations from N Elements
n Total Number of Items
k Number of Items to Choose

Permutations
P(n, k) = n! / (n-k)!
P(n, k) Number of K Permutations from N Elements
n Total Number of Items
k Number of Items to Arrange

Bayes Theorem
P(A|B) = P(B|A) × P(A) / P(B)
P(A|B) Probability of A Given B
P(B|A) Probability of B Given A
P(A) Probability of A
P(B) Probability of B

Euclidean Distance
d = √((x₂-x₁)² + (y₂-y₁)²)
d Distance Between Two Points
x₁ X Coordinate of Point One
y₁ Y Coordinate of Point One
x₂ X Coordinate of Point Two
y₂ Y Coordinate of Point Two

Manhattan Distance
d = |x₂-x₁| + |y₂-y₁|
d Distance Between Two Points
x₁ X Coordinate of Point One
y₁ Y Coordinate of Point One
x₂ X Coordinate of Point Two
y₂ Y Coordinate of Point Two

Hamming Distance
Number of Positions Where Corresponding Symbols Differ
Positions Index Locations in Strings
Symbols Characters or Bits

Jaccard Similarity
J(A,B) = |A ∩ B| / |A ∪ B|
J(A,B) Jaccard Similarity Coefficient
A First Set
B Second Set
∩ Set Intersection
∪ Set Union

Cosine Similarity
cos(θ) = (A · B) / (||A|| × ||B||)
θ Angle Between Vectors A and B
A · B Dot Product of Vectors A and B
||A|| Magnitude of Vector A
||B|| Magnitude of Vector B

Dot Product
A · B = Σ (Aᵢ × Bᵢ)
A · B Dot Product of Vectors A and B
Aᵢ Ith Component of Vector A
Bᵢ Ith Component of Vector B

Algorithms

Euclidean Algorithm
gcd(a, b) = gcd(b, a mod b)
gcd Greatest Common Divisor
a First Integer
b Second Integer
a mod b Remainder of a Divided by b

Modular Arithmetic
a ≡ b (mod m)
a Congruent to b Modulo m
b Congruent to a Modulo m
m Modulus

Modular Addition
(a + b) mod m = (a mod m + b mod m) mod m
a First Integer
b Second Integer
m Modulus

Modular Multiplication
(a × b) mod m = (a mod m × b mod m) mod m
a First Integer
b Second Integer
m Modulus

Modular Exponentiation
aᵇ mod m
a Base
b Exponent
m Modulus

Bubble Sort
Repeatedly Swap Adjacent Elements If in Wrong Order
Swap Exchange Two Elements
Adjacent Elements Next to Each Other

Selection Sort
Repeatedly Find Minimum Element and Put at Beginning
Minimum Element Smallest Element in Unsorted Part

Insertion Sort
Build Sorted Array One Element at a Time by Inserting in Correct Position
Inserting Placing Element in Correct Spot in Sorted Part

Merge Sort
Divide Array into Halves Recursively Sort Then Merge
Divide Split the Array
Merge Combine Two Sorted Arrays into One

Quick Sort
Choose Pivot Partition Array Around Pivot Recursively Sort Partitions
Pivot Element Chosen to Partition Array
Partition Rearrange So Elements Less Than Pivot Come Before Elements Greater Than Pivot

Heap Sort
Build Max Heap Repeatedly Extract Maximum Element
Max Heap Complete Binary Tree Where Parent Is Greater Than Children
Extract Maximum Remove Largest Element

Linear Search
Check Each Element Sequentially Until Target Is Found
Sequentially One After the Other
Target Value Being Searched For

Binary Search
Repeatedly Check Middle Element of Sorted Array and Eliminate Half
Middle Element Element at Center Index
Sorted Arranged in Order

Depth First Search
Explore as Far as Possible Along Each Branch Before Backtracking
Explore Visit a Node
Backtracking Going Back to Previous Node

Breadth First Search
Explore All Nodes at Present Depth Before Moving to Next Level
Depth Distance from Starting Node
Level Set of Nodes at Same Depth

Dijkstra Algorithm
Find Shortest Path from Source to All Nodes in Weighted Graph Without Negative Weights
Shortest Path Path with Smallest Total Weight
Weighted Graph Graph with Costs Associated with Edges

Bellman Ford Algorithm
Find Shortest Path from Source Allowing Negative Weights Detect Negative Cycles
Negative Cycles Cycles Where Total Weight Is Negative

Floyd Warshall Algorithm
Find Shortest Paths Between All Pairs of Nodes
All Pairs Every Possible Combination of Start and End Node

Prim Algorithm
Find Minimum Spanning Tree by Growing from Start Node Adding Cheapest Edge
Minimum Spanning Tree Tree Connecting All Nodes with Minimum Total Weight

Kruskal Algorithm
Find Minimum Spanning Tree by Adding Edges in Increasing Weight Without Cycles
Increasing Weight From Smallest to Largest Cost

Topological Sort
Linear Ordering of Vertices in Directed Acyclic Graph Where for Every Edge u→v u Comes Before v
Directed Acyclic Graph Graph with Directed Edges and No Cycles

Kadane Algorithm
max_ending_here = max(num, max_ending_here + num)
max_ending_here Maximum Sum of Subarray Ending at Current Index
num Current Array Element

Maximum Subarray
max_so_far = max(max_so_far, max_ending_here)
max_so_far Overall Maximum Sum
max_ending_here Maximum Sum of Subarray Ending at Current Index

Quickselect Algorithm
Use Partition from Quicksort to Find Kth Smallest Element
Partition Rearranges Array Around Pivot

Hamming Weight
Number of 1 Bits in Binary Number
Binary Number Represented in Base Two

Gray Code
Binary Numeral System Where Two Successive Values Differ in Only One Bit
Successive Consecutive Numbers

Data Structures

Binary Tree Node Structure
Node Has Data Left Child Pointer Right Child Pointer
Data Value Stored
Left Child Pointer Points to Left Subtree
Right Child Pointer Points to Right Subtree

Binary Tree Inorder Traversal
Traverse Left Subtree Visit Root Traverse Right Subtree
Visit Process the Node

Binary Tree Preorder Traversal
Visit Root Traverse Left Subtree Traverse Right Subtree
Visit Process the Node

Binary Tree Postorder Traversal
Traverse Left Subtree Traverse Right Subtree Visit Root
Visit Process the Node

Binary Search Tree Insert
If Tree Empty Create Node Else If Value Less Than Root Insert Left Else Insert Right
Tree Empty Root Is Null
Create Node Allocate Memory and Set Value

Binary Search Tree Search
If Root Null Return Null Else If Value Equals Root Return Root Else If Value Less Search Left Else Search Right
Root Null Tree Is Empty

Binary Search Tree Delete
Find Node If No Children Remove If One Child Bypass If Two Children Find Inorder Successor Copy and Delete Successor
Inorder Successor Next Node in Inorder Traversal

AVL Tree Balance Factor
Balance Factor = Height(Left Subtree) – Height(Right Subtree)
Balance Factor Must Be Between Negative One and One for Tree to Be Balanced
Height Longest Path from Node to Leaf

Hash Function
h(key) = key mod m
h(key) Hash Value
key Value to Be Hashed
m Size of Hash Table

Hash Table Chaining
Store Colliding Elements in Linked List at Same Index
Colliding Elements Different Keys That Map to Same Index

Hash Table Open Addressing
Find Next Open Slot Using Probing When Collision Occurs
Probing Method to Find Alternative Index

Linear Probing
h(key, i) = (h'(key) + i) mod m
i Probe Number
h'(key) Primary Hash Function

Quadratic Probing
h(key, i) = (h'(key) + c₁×i + c₂×i²) mod m
c₁ Constant
c₂ Constant
i Probe Number

Double Hashing
h(key, i) = (h₁(key) + i × h₂(key)) mod m
h₁ First Hash Function
h₂ Second Hash Function

Stack Push Operation
Add Element to Top of Stack
Top Most Recently Added Element

Stack Pop Operation
Remove and Return Top Element from Stack
Top Most Recently Added Element

Queue Enqueue Operation
Add Element to Rear of Queue
Rear End of the Queue

Queue Dequeue Operation
Remove and Return Front Element from Queue
Front Beginning of the Queue

Linked List Insert
Create New Node Set Next Pointer Insert at Desired Position
New Node Node to Be Inserted
Next Pointer Points to Following Node

Linked List Delete
Find Node Adjust Pointers of Previous Node to Skip It Free Memory
Adjust Pointers Change Next Pointer of Previous Node

Graph Representation Adjacency Matrix
Two Dimensional Array Where Matrix[i][j] Is One If Edge from i to j Else Zero
i Source Vertex
j Destination Vertex

Graph Representation Adjacency List
Array of Lists Where List[i] Contains All Vertices Adjacent to i
Adjacent Vertices Connected by Edge

Dynamic Programming

Dynamic Programming Fibonacci
dp[0] = 0, dp[1] = 1, dp[i] = dp[i-1] + dp[i-2] for i≥2
dp[i] Ith Fibonacci Number

Zero One Knapsack
dp[i][w] = max(value[i] + dp[i-1][w-weight[i]], dp[i-1][w])
dp[i][w] Maximum Value for First i Items with Capacity w
value[i] Value of Item i
weight[i] Weight of Item i

Longest Common Subsequence
if str1[i] == str2[j] then dp[i][j] = 1 + dp[i-1][j-1] else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
dp[i][j] Length of LCS of First i Characters of str1 and First j Characters of str2

Matrix Chain Multiplication
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]×p[k]×p[j]) for k from i to j-1
dp[i][j] Minimum Cost to Multiply Matrices from i to j
p Array of Dimensions

Edit Distance
if str1[i] == str2[j] then dp[i][j] = dp[i-1][j-1] else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
dp[i][j] Minimum Operations to Convert First i Characters of str1 to First j Characters of str2

Coin Change Number of Ways
dp[i] += dp[i – coin] for each coin in coins
dp[i] Number of Ways to Make Amount i

Coin Change Minimum Coins
dp[i] = min(dp[i], 1 + dp[i – coin]) for each coin in coins if i≥coin
dp[i] Minimum Coins to Make Amount i

Cryptography

RSA Encryption
Ciphertext = Plaintextᵉ mod n
Ciphertext Encrypted Message
Plaintext Original Message
e Public Encryption Exponent
n Modulus Product of Two Primes

RSA Decryption
Plaintext = Ciphertextᵈ mod n
Plaintext Original Message
Ciphertext Encrypted Message
d Private Decryption Exponent
n Modulus Product of Two Primes

Diffie Hellman Key Exchange
Shared Secret = (gᵃᵇ) mod p
Shared Secret Symmetric Key
g Primitive Root Modulo p
a Alice Private Key
b Bob Private Key
p Large Prime Number

SHA Two Fifty Six
Cryptographic Hash Function Producing Two Hundred Fifty Six Bit Hash Value
Cryptographic Secure for Digital Signatures

MD Five
Cryptographic Hash Function Producing One Hundred Twenty Eight Bit Hash Value
Cryptographic Secure for Digital Signatures

Base Sixty Four Encoding
Represent Binary Data as ASCII Text Using Sixty Four Character Alphabet
ASCII Text Human Readable Characters

Checksum
Sum of Data Bits Used for Error Detection
Error Detection Identifies If Data Has Been Corrupted

Cyclic Redundancy Check
Compute Remainder of Polynomial Division of Data by Generator Polynomial
Remainder CRC Value
Generator Polynomial Predetermined Divisor

Computer Architecture

Floating Point Representation
(-1)ˢ × m × 2⁽ᵉ⁻ᵇⁱᵃˢ⁾
s Sign Bit
m Mantissa
e Exponent
bias Constant to Allow Negative Exponents

IEEE Seven Five Four Single Precision
One Bit Sign Eight Bits Exponent Twenty Three Bits Mantissa
Sign Bit Determines Positive or Negative
Exponent Stored with Bias of One Hundred Twenty Seven
Mantissa Fractional Part

IEEE Seven Five Four Double Precision
One Bit Sign Eleven Bits Exponent Fifty Two Bits Mantissa
Sign Bit Determines Positive or Negative
Exponent Stored with Bias of One Thousand Twenty Three
Mantissa Fractional Part

Two Complement
Negative Number Represented by Inverting Bits and Adding One
Inverting Bits Changing Zero to One and One to Zero

Bitwise AND
result = a & b
& Bitwise AND Operator
a First Operand
b Second Operand

Bitwise OR
result = a | b
| Bitwise OR Operator
a First Operand
b Second Operand

Bitwise XOR
result = a ^ b
^ Bitwise XOR Operator
a First Operand
b Second Operand

Bitwise NOT
result = ~a
~ Bitwise NOT Operator
a Operand

Left Shift
result = a << b
<< Left Shift Operator
a Value to Shift
b Number of Positions to Shift

Right Shift
result = a >> b
>> Right Shift Operator
a Value to Shift
b Number of Positions to Shift

Power of Two Check
n > 0 and (n & (n-1)) == 0
n Positive Integer
& Bitwise AND Operator

Networking

Little Law
L = λ × W
L Average Number of Items in System
λ Average Arrival Rate
W Average Time Item Spends in System

Round Robin Scheduling
Allocate CPU Time in Circular Order to Each Process in Queue
CPU Time Processor Time

Paging
Divide Memory into Fixed Size Pages Map Virtual Addresses to Physical Frames
Virtual Address Generated by CPU
Physical Frame Block of RAM

Page Replacement FIFO
Evict Page That Has Been in Memory Longest
Evict Remove from Memory

Page Replacement LRU
Evict Least Recently Used Page
Evict Remove from Memory

Belady Anomaly
Page Fault Rate May Increase as Number of Frames Increases
Page Fault Occurs When Needed Page Is Not in Memory

Hamming Code
Error Correcting Code That Can Detect and Correct Single Bit Errors
Error Correcting Code Can Identify and Fix Errors in Data

CRC Polynomial Division
Divide Message Polynomial by Generator Polynomial Keep Remainder as Checksum
Message Polynomial Binary Data Represented as Polynomial
Generator Polynomial Predetermined Divisor Polynomial

Theory of Computation

Halting Problem
Determining Whether Program Will Finish Running or Continue Forever Is Undecidable
Undecidable No Algorithm Can Solve It for All Inputs

Church Turing Thesis
Any Function Computable by Algorithm Is Computable by Turing Machine
Turing Machine Mathematical Model of Computation

P vs NP
Asks Whether Every Problem Verifiable in Polynomial Time Can Also Be Solved in Polynomial Time
Polynomial Time Runtime Is O(nᵏ) for Some Constant k

Lambda Calculus
Function Definition and Application Using Variable Binding and Substitution
Variable Binding Associates Variable with Expression

Moore Law
Number of Transistors on Chip Doubles Approximately Every Two Years
Transistor Semiconductor Device

CAP Theorem
Distributed System Can Only Provide Two of Consistency Availability Partition Tolerance
Consistency All Nodes See Same Data
Availability Every Request Receives Response
Partition Tolerance System Continues Despite Network Partitions

Unix Epoch Time
Number of Seconds Since January 1 1970 000000 UTC
UTC Coordinated Universal Time

Unix File Permissions
Read Write Execute for Owner Group Others
Read Permission Allows Viewing File Content
Write Permission Allows Modifying File Content
Execute Permission Allows Running File