Practice set for DSA Lecture 2. Read the full lesson first: Time Complexity and Big-O Notation Explained Simply on eLecturesAI.
Reading a topic and knowing a topic are two different things. The quickest way to find out which one you have is to answer questions without looking at your notes.
This page has 15 MCQs, 5 short questions and a score guide, all based on DSA Lecture 2: why we count steps, Big-O notation, best, average and worst case, O, Ω and Θ, counting steps in loops, and space complexity.
- Click the option you think is correct. It turns green if you are right and red if you are wrong.
- Read the explanation that opens under the question.
- If you got it wrong, use the Revise link to go back to that exact part of the lesson.
- Check your score at the end and follow the guide.
Section 1: Why analyze algorithms and Big-O basics
Q1Why do we count steps instead of measuring seconds when we compare algorithms?
Show answer
Answer: B. A fast computer can make a bad algorithm look good. Counting basic steps as a function of n gives a fair comparison that does not depend on the machine.
Q2Version B of the sum, sum = n * (n + 1) / 2;, takes about how many steps, however big n is?
Show answer
Answer: C. It is a single formula, so the work does not grow with n. Version A (the loop) needs about n steps.
Revise: Why analyze algorithms?
Q3What is the Big-O of 3n² + 5n + 2?
Show answer
Answer: A. Drop the smaller terms (5n and 2), then drop the constant multiplier (3). Only the fastest-growing term, n², remains.
Revise: Keep only the biggest term
Q4A sorted list of 1 billion books is searched by halving it at every step. About how many steps are needed?
Show answer
Answer: D. Halving a billion about 30 times leaves 1 item. That is O(log n), and it works only on sorted data.
Revise: Big-O: how fast does it grow?
Q5What is the Big-O of reading the array element a[5]?
Show answer
Answer: B. Jumping straight to a known position is one step, however big the array is. This is constant time, like the index sending you straight to Shelf D.
Revise: Big-O: how fast does it grow?
Section 2: Best, average and worst case, and the bounds
Q6In a heap of 10,000 books, linear search finds the DSA book as the very first book. How many steps does it take?
Show answer
Answer: D. This is the best case: the item is at the front, so one comparison is enough.
Revise: Best, average and worst case
Q7For the same heap of 10,000 books, about how many steps does linear search take on average?
Show answer
Answer: B. On average the item is somewhere in the middle, so you check about n/2 books, which is 5,000.
Revise: Best, average and worst case
Q8Which situation is the worst case of linear search?
Show answer
Answer: C. If the book is last or missing, you must check all n books before you can say so. That is n steps, so O(n).
Revise: Best, average and worst case
Q9Which statement about the three bounds is correct?
Show answer
Answer: A. Think of a school trip that takes at least 10 and at most 30 minutes. O says never more than 30, Ω says never less than 10, and Θ is used when the upper and lower bounds match.
Revise: Big-O, Omega and Theta
Q10Which case do we usually quote in this course, and why?
Show answer
Answer: D. The worst case is a promise you can plan around, like leaving home 30 minutes early because of possible traffic.
Revise: Best, average and worst case
Section 3: Counting steps, rules and space
Q11What is the Big-O of a loop that runs n times with another loop of n iterations inside it?
Show answer
Answer: C. A loop inside a loop multiplies: n × n. For n = 3 that is 9 steps, like checking every book against every other book.
Revise: Counting steps in code
Q12What does int i = 1; while (i < n) i = i * 2; do for n = 16, and what is its Big-O?
Show answer
Answer: A. The variable doubles: 1, 2, 4, 8, and then 16 stops the loop. That is 4 runs, which is log2(16). Doubling or halving means O(log n).
Revise: Counting steps in code
Q13One part of a program takes O(n) steps, and a second part, run after it, takes O(n²) steps. What is the total?
Show answer
Answer: B. Steps one after another are added, and the biggest term wins: n + n² becomes O(n²).
Revise: Rules for combining steps
Q14How much extra space does a copy of an array of n items need?
Show answer
Answer: C. A few variables are O(1) extra space, but a full copy of an n-item array needs room for n items, which is O(n).
Q15A library index needs an extra register but makes finding a book very fast. What is this idea called?
Show answer
Answer: D. Using more memory to save time is the space-time trade-off. Database indexes and the index at the back of a textbook work the same way.
Short questions (write the answers in your own words)
Don’t just read these. Write each answer on paper in 2-3 lines, then compare.
S1. Why do we count steps instead of seconds when we compare algorithms?
Show model answer
Seconds depend on the computer, how busy it is and (in our story) how fast the person walks. Steps belong to the algorithm itself, so counting them as a function of the input size n gives a fair comparison. In the library, one step means checking one book.
S2. Find the Big-O of 4n² + 7n + 9 and name the two rules you used.
Show model answer
The answer is O(n²). Rule 1: drop the smaller terms (7n and 9 become tiny as n grows). Rule 2: drop the constant multiplier (the 4 does not change the shape of the growth).
S3. Linear search looks for the DSA book in a heap of 10,000 books. Give the best, average and worst case, and say which one we usually quote.
Show model answer
Best case: the first book, 1 step. Average case: about 5,000 steps. Worst case: the last book or not there at all, 10,000 steps, which is O(n). We usually quote the worst case because it is a guarantee that the search will never be slower than this.
S4. Explain why a loop inside a loop is O(n²). Use n = 3 as an example.
Show model answer
The outer loop runs n times, and for each of those runs the inner loop also runs n times, so the total is n × n. For n = 3 that is 3 × 3 = 9 steps. It is like comparing every book with every other book. Two loops one after another would only add up to O(n).
S5. Explain the space-time trade-off using the library index.
Show model answer
The index needs extra space (an extra register), but finding a book becomes very fast, so we use more space to save time. Without the index we save space, but every search is a long walk through the heap, which is O(n). Database indexes work the same way.
Check your score
Count your correct MCQs (out of 15):
| Score | What it means | What to do next |
|---|---|---|
| 14 – 15 | Excellent. The concepts are solid. | Move on to the next lecture. |
| 11 – 13 | Good, with a few gaps. | Re-read only the sections linked under the questions you missed. |
| 8 – 10 | Half-way there. | Read the lesson again slowly, then retry this quiz tomorrow. |
| Below 8 | The basics are not settled yet. | Read the full lesson once more, work out the Big-O of the three loop examples yourself, then retake the quiz. |
Go back to the full lesson: Time Complexity and Big-O Notation Explained Simply →
Frequently asked questions
Are these MCQs enough for the exam?
They cover the whole of Lecture 2, but real exams also ask you to write short answers and work out the Big-O of code. Practice the five short questions above as well.
What is the best way to use an MCQ quiz?
Answer first, check later. Reading the answer without trying the question gives a false feeling of knowing it.
Where do I learn the topic if I got most answers wrong?
Start with the lesson on eLecturesAI: Time Complexity and Big-O Notation Explained Simply. Each question above also links to the exact section to revise.
Written by Engnr.Dr. Muhammad Tahir Dlbar
Leave a Reply