Runtime Complexity Flashcards
Describe “N” or Linear runtime.
It is when there is a direct correlation between the amount of inputs into the algorithm and the amount of work needed to be done.
Example: a function taking a string as an arg and processes each element
Describe “N^2” or Quadratic runtime.
It is when n increases and much more work is done per n.
Example is when there is a nested for loop
Describe “log(n)” or Logarithmic runtime.
This is when doubling the number of elements to iterate over does not double the amount of work. Always assume searching algorithms are log(n)
In Big O Notation, what is O(n)?
Linear Runtime
In Big O Notation, what is O(1)?
Constant Runtime
In Big O Notation, what is O(n^2)?
Quadratic Runtime
What is the runtime of your algorithm if you are iterating over a single collection?
Linear or O(n)
What is the runtime of your algorithm if you are iterating over 2 different collections in 2 separate for loops?
O(n +m)
What is the runtime of your algorithm if you have nested for loops iterating over the same collection?
Quadratic or O(n^2)
What is the runtime of your algorithm if you have nested for loops iterating over different collections?
O(n * m)
What is the runtime of a sorting algorithm?
O(n*log(n))
What is the runtime of a searching algorithm?
O(log(n))
What is space complexity?
The amount of memory used to complete a task
What is the time complexity of the Fibonacci iterative solution?
Linear if using memoization, otherwise its exponential
What is the time complexity of the Fibonacci recursive solution?
Exponential
How do you optimize the Fibonacci algorithm?
Use memoization:
- Code the existing fib function
- Code a memoization function that take the fib func as argument
- If the args have been called before, return cache version
- If not, call the fn using apply with the args
What is the time complexity of BFS and DFS?
O(V + E)
What is the time complexity of sliding window?
O(n)
