Time Complexities

Question 1

What is Constant time complexity?

Answer 1

• O (1)
• Time is independent of input
• Example: Determining if a number is odd / even.

Question 2

What is Linear time complexity?

Answer 2

• O (n)
• Worst case scenario: must go through each item once.
• Example: Linear search

Question 3

What is Polynomial time complexity?

Answer 3

• O (n²)
• A loop inside a loop
• Example: Bubble sort

Question 4

What is a Logarithmic time complexity?

Answer 4

• O (logn)
• Halves the number of items in each iteration
• Example: Binary search

Question 5

What is a Linear Logarithmic time complexity?

Answer 5

• O (nlogn)
• N / A
• Example: Merge sort

Question 6

What is an Exponential time complexity?

Answer 6

• O (2^n)
• Intractable
• Example: Recursively calculating Fibonacci numbers

Question 7

What is a Factorial time complexity?

Answer 7

• O (n!)
• Intractable
• Example: Travelers problem