Algorithm Analysis Flashcards
O(1)
Constant Time
O(log n)
Logarithmic TIme
O(n)
Linear TIme
O(n log n)
N Log N Time
O(n^p)
Polynomial Time
O(k^n)
Exponential Time
O(n!)
Factorial Time
Time proportional to input size
Constant Time
Time proportional to the logarithm of the input
Logarithmic Time
Time linearly proportional to the size of the input
Linear Time
Time proportional to n log n of input
N Log N Time
Time proportional to polynomial exponent of input
Polynomial Time
Time proportional to exponential growth of input
Exponential Time
Time proportional to factorial of input
Factorial Time
Loop running time is at most
The running time of the statements inside the loop multiplied by the number of iterations
Nested loop running time is at most
The product of the running time of all the loops
Consecutive statements have the complexity
Of each of the statement’s running times added together
If-then-else statements worst-case complexities equals
The test, plus either the then or the else part (whichever is larger)
log x^y
y log x
log xy
log x + log y
log log n
log(log n)
log^k n
(log n)^k
log (x / y)
log x - log y
Amortized Analysis
Determining the time-averaged running time for a sequence of operations
