Time Complexities Flashcards
1
Q
What is Constant time complexity?
A
- O (1)
- Time is independent of input
- Example: Determining if a number is odd / even.
2
Q
What is Linear time complexity?
A
- O (n)
- Worst case scenario: must go through each item once.
- Example: Linear search
3
Q
What is Polynomial time complexity?
A
- O (n²)
- A loop inside a loop
- Example: Bubble sort
4
Q
What is a Logarithmic time complexity?
A
- O (logn)
- Halves the number of items in each iteration
- Example: Binary search
5
Q
What is a Linear Logarithmic time complexity?
A
- O (nlogn)
- N / A
- Example: Merge sort
6
Q
What is an Exponential time complexity?
A
- O (2^n)
- Intractable
- Example: Recursively calculating Fibonacci numbers
7
Q
What is a Factorial time complexity?
A
- O (n!)
- Intractable
- Example: Travelers problem
