General Time Complexity Flashcards
What is “Big O” notation?
f(n) is O(g(n)) as n → ∞
An upper-bound approximation of the behavior of f(n) as n approaches infinity
What are the 6 main types of Big O?
O(1)O(log₂ n)O(n)O(n log n)O(n²)O(2ⁿ)
What are the 4 rules of Big O?
- Assume worst case scenario
- Remove constants
- Remove non-dominants
- Different inputs require different identifiers
What is the time complexity for:
obj.method(n, o) {
n.forEach(...);
o.forEach(...);
}
O(n + o)
What is the time complexity for:
obj.method(n) {
n.forEach(e -> n.forEach(...));
O(n^2)
What is the time complexity for:
obj.method(n) {
n.forEach(...);
n.forEach(e -> n.forEach(...));
}
O(n^2)
What is the time complexity for:
obj.method(n, o) {
n.forEach(e -> o.forEach(...));
}
O(n * o)
What does “amortized constant time” mean?
It means O(1) most of the time, but O(n) in rare occasions. An example would be dynamic arrays that have readhed their capacity
- What is the time complexity of a binary search algorithm?
- What are the 2 requirements for using a binary search algorithm?
- O(log(n))
- Sorted data
Or - A binary decision to reduce search range by half
- Sorted data
What are the different ways to think about O(log n)?
- As n doubles, the number of operations increases by 1
- The number of operations can be determined by continuously dividing n by 2 until it produces a value <= 1
Logarithms are the inverse of…
Exponents
For example:
2^3 = 2 * 2 * 2
is the inverse of
log(8) = 8/2 4/2 2/2
Could 2 different algorithms with the same Big O have different speeds?
Yes
Describe how to analyze the time complexity of a recursive algorithm
For each recursive invocation, account for the number of operations performed within its body. Multiply that sum by the number fo recursive invocations performed. (This is also how a person would analyze the time complexity of an algorithm that calls another method)
What is the purpose of Big O?
The purpose of Big O is to classify the computational complexity of an algorithm
What is time complexity?
Time complexity is the amount of time an algorithm needs to compute relative to the input size
