What type of algorithm is O(1)?
An algorithm that takes a constant amount of time regardless of input data
What type of algorithm is O(n)?
An algorithm that takes linear time
What happens as input size increases in O(n)?
Number of instructions to be completed grows proportionally
What is an example of O(n) in coding?
For and while loops
What type of algorithm is O(n^2)?
Algorithm that takes a square time to complete
What is the performance of O(n^2) proportional too?
(data inputs)^2
What sorting algorithm uses O(n^2)?
Bubble sort
What’s an example of O(n^2) in coding?
Nested loops
e.g.
x = 12
for i = 1 to x
for j = 1 to
next j
next i
What would O(n^6) look like?
The power is the amount of loops
for a = 1 to n
for b = 1 to n
for c = 1 to n
for d = 1 to n
for e = 1 to n
for f = 1 to n
next f
next e
next d
next c
next b
next a
What type of algorithm is O(2^n)?
An algorithm that takes double the time to for each added data input
Why is O(2^n) not used as much?
It’s inefficient but some problems can only be solved in exponential time
What algorithms use O(2^n)?
Recursive function with two calls
Fibonacci sequence with recursion
What type of algorithm is O(logn)?
An algorithm that takes very little time as the size of the input grows larger.
What is the base log for O(logn)
Base 2 NOT 10
What sorting algorithm is an example of O(logn)?
Binary search
What are the O notations ranked from least efficient to most efficient?
O(2^n)
O(n^2)
O(n)
O(logn)
O(1)
Whats the best time complexity for all the searching algorithms?
O(1)
Whats the worse time complexity for a linear search, binary search tree and hashing?
O(n)
Whats the worse time complexity for
