Big O notation Flashcards
Big O Constant Time (random access in array)
O(1) Constant Time
Big O Linear Time (Delete value linked List)
O(n) Linear Time (Looping Arrays, Lists)
What is Big O Notation
1) The efficiency of your Algorithm
2) Used to describe run-time characteristics of our data structure and algorithms
What is linear time
Where the number of elements in the data structure increased and the operation takes longer (looping, etc)
What is faster O(n) or O(2^n)
O(n)
Big O What is Logarithmic (search algorithms)
O(Log n) Logarithmic
Big O What is Quasilinear ( Sorting algorithms)
O(n log n) Quasilinear
Big O What is Quadratic (Nested Loops )
O(n powerOf 2) Quadratic
Exponential (Recursion, Fibonacci series) Gets slower the more that is calculated
O(2 powerOf n) Recursion,
Operations that takes the same amount of time regardless of the number of elements
O(1)
Iteration through a collection (for loop, while loop)
O(n)
Looping through the same collection x2 (nested)
O(n powerOf 2)
Fibonacci series - recursion (branches squared depth)
O(2 powerOf n)
Search sorted array (binary tree)
O(log n)
simplify O(n powerOf 2 + n)
O(n powerOf) Drop non-dominated terms
simplify O(3n)
O(n) Drop constants
Describe two Loops
O(n+m)
Nested for Loop two different arrays
O(n*m)
Nest for Loop with same array
O(n powerOf 2)
Big O
Constant
O(1)
Big O
Logarithmic
O(log n)
Big O
Linear
O(n)
Big O
Log Linear
O(n log n)
Big O
Quadratic
O(n^2)
O(n powerOf 2)
Big O
Cubic
O(n^3)
Big O
Exponential
O(2^n)
Big O simplify
O(1) + (O(n/2)) = O (1/2 *n) + O(10)
print 1st[0] # O(1)
midpoint = len(1st)/2 # O(1/2 * n)
for val in list[:midpoint]:
print (val)
for x in range(10) # O(10)
print(‘hello world’)
O(1) + (O(n/2)) = O (1/2 *n) + O(10)
# O(1 + n/2 + 10) # AS IT GROWS lARGER 1 AND 10 BECOME INSUGNIFICATE # o(n)
Big O
n*n (two for loops)
n squared
O(n^2)
dangers for large inputs
Big O
Only do an action once
O(1)
Big O - Python
Lists
Indexing and Assigning
O(1)
Big O - Python
Dictionary
O(1)
