Common complexity classes (O(1), O(n), O(log n), O(n²)) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does O(1) mean in complexity classes?

O(1) means constant time complexity. The time to complete the task does not change no matter how big the input is. For example, accessing a single item in a list by its index.

beginner

Explain O(n) complexity with a real-life example.

O(n) means linear time complexity. The time grows directly with the size of the input. For example, checking each item in a shopping list one by one.

intermediate

What does O(log n) complexity represent?

O(log n) means logarithmic time complexity. The time grows slowly as input size increases, often by cutting the problem in half each step. For example, finding a word in a dictionary by opening near the middle and narrowing down.

intermediate

Describe O(n²) complexity and when it might happen.

O(n²) means quadratic time complexity. The time grows with the square of the input size. For example, comparing every student with every other student in a class to find pairs.

beginner

Why is understanding complexity classes important?

Understanding complexity helps us predict how fast or slow an algorithm will run as data grows. It helps choose efficient solutions and avoid slow programs.

Which complexity class means the running time does not change with input size?

A O(1)

B O(n)

C O(log n)

D O(n²)

O(1) means constant time, so the running time stays the same regardless of input size.

If an algorithm checks every item in a list once, what is its complexity?

A O(n)

B O(1)

C O(log n)

D O(n²)

Checking each item once means the time grows linearly with input size, which is O(n).

Which complexity is typical for binary search?

A O(n²)

B O(n)

C O(log n)

D O(1)

Binary search cuts the search space in half each step, leading to O(log n) complexity.

What does O(n²) complexity imply about the number of operations?

A Operations grow linearly

B Operations grow logarithmically

C Operations stay constant

D Operations grow with the square of input size

O(n²) means the number of operations grows with the square of the input size.

Why should we avoid algorithms with high complexity for large data?

A They run faster

B They can become very slow and inefficient

C They use less memory

D They are easier to understand

High complexity algorithms can become very slow as data grows, making them inefficient.

Explain the differences between O(1), O(n), O(log n), and O(n²) complexity classes with simple examples.

Think about how the time changes as input size grows.

Why is it important to understand complexity classes when choosing algorithms?

Consider the impact on speed and resources.