Big O Notation Flashcards
2.3.1
What is the point of Big-O Notation?
To find the upper bound of the function’s growth rate. Essentially the longest time it takes to turn the input into an output.
What is Big-O a measure of?
Time Complexity
What is Constant Complexity?
The algorithm always takes the same amount of time to execute, regardless of the size of the data.
What is the notation for constant complexity?
O(1)
What is an example of Constant Complexity?
Print Statements:
print(“hello world”)
What is Linear Complexity?
The time taken to execute an algorithm is directly proportional to the size of the data. So as the size of the data doubles, so does the time taken to execute.
What is the notation for Linear Complexity?
O(n)
What is an example of Linear Complexity?
For Loops:
for item in list:
print(item)
What is Polynomial Complexity?
The amount of time taken to complete an algorithm is directly proportional to the square of the size of the data set
What is the notation for Polynomial Complexity?
O(n^2)
What is an example of Polynomial Complexity?
Nested For Loops (within other For Loops):
for items in list:
for items in list:
print(items)
What is exponential complexity?
The amount of time taken to complete an algorithm will double with every additional element
What is the notation for Exponential Complexity?
O(2^n)
What is an example of an Exponential Complexity?
Recursive Functions:
def algo(items):
x = int(items)
if x <= 1:
return x
return algo(x-2) + algo(x-1)
What is Logarithmic Complexity?
The time taken to execute the algorithm is proportional to the logarithmic result (log) of the input size.
