Big O Notation Flashcards
What is Big O Notation?
the language we use to talk about how efficient an algorithm is
What is constant time?
The time doesn’t change relative to input size
What is the notation for constant time?
O(1)
O(1) is what BigO notation?
Constant Time
What is linear time?
The time will change at the same rate as the input
Give a code example of linear time
A func that prints every item of an array:
func printAllItems(in items: [Int]) {
for item in items {
print(item)
}
}
Give a code example of constant time
Accessing one element in an array by index:
func printFirstItem(in items: [Int]) {
print(items[0])
}
What is the notation for linear time?
O(n)
O(n) is what BigO notation?
Linear time
What is quadratic time?
The time required to execute a command is square of the input
What is the notation for quadratic notation?
O(n^2)
O(n^2) is what BigO notation?
Quadratic notation
Give a code example of quadratic notation?
Iterating over nested loops:
func printAllPossibleOrderedPairs(in items: [Int]) {
for firstItem in items {
for secondItem in items {
print(firstItem, secondItem)
}
}
}
Is BigO usually concerned with Worst, Average, or Best case scenarios?
Worst
What are the two complexities that BigO can refer to?
Time and Space
Identify the time complexity:
func printAllPossibleOrderedPairs(in items: [Int]) {
for firstItem in items {
for secondItem in items {
print(firstItem, secondItem)
}
}
}
Quadratic, O(n^2), because theres nested loops
Identify the time complexity:
Accessing one element in an array by index:
func printFirstItem(in items: [Int]) {
print(items[0])
}
O(1), constant
Identify the time complexity:
func printAllItems(in items: [Int]) {
for item in items {
print(item)
}
}
Linear, O(n)
Free card
Have some good karma
What is the time complexity of an array lookup by index?
O(1)
What is the time complexity of a hash lookup?
O(1) on average bc of potential collisions
What is x?
x = log(2, 16)
4
What is x?
x = log(3, 9)
2
What is x?
x = log(5, 25)
2
What is the notation for a logarithmic algorithm?
O(log n)
O(log n) is what BigO notation?
Logarithmic
Give an example of a logarithmic algorithm and explain why
Binary Search because each step exponentially reduces the input size
A logarithm is the inverse function to what?
exponents
What is the time complexity of binary search? why?
O(log n) because the search input decreases in size logarithmically
Identify the bigO notation and explain why
for i in stride(from: 0, to: n, by: 1) {
for j in stride(from: 1, to: n, by: 1) {
for k in stride(from: 1, to: n, by: 1) {
// do constant time stuff
}
}
}
O(n^3), cubic, because theres 3 levels of nested loops
Identify the notation:
it only takes a single step for the algorithm to accomplish the task.
Constant: O(1)
Identify the notation:
The number of steps it takes to accomplish a task are decreased by some factor with each step.
Logarithmic: O(log n)
Identify the notation:
The number of of steps required are directly related to the input
Linear: O(n)
Identify the notation:
The number of steps it takes to accomplish a task is square of n
Quadratic: O(n^2)
Identify the notation:
The number of steps it takes to accomplish a task is a constant to the n power (pretty large number)
Exponential: O(k^n)
What is a logarithm?
The power that a number needs to be raised to in order to get another number
Define: The power that a number needs to be raised to in order to get another number
Logarithm
What is the time complexity for an algorithm that calculates a Fibonacci number using recursion? and why?
exponential, o(2^n), because each iteration calls itself twice. Because the iteration returns ( fib(n-1) + fib(n-2) ).
Which function is the inverse of exponential?
Logarithmic
Which function is the inverse of logarithmic?
Exponential
Whats the difference between quadratic notation and exponential notation?
quadratic == n^2
exponential == x^y
