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
