RG's E-Learning Centre · Book a free demo class · WhatsApp +91-9379416374

Counting operations and Big-O: Class 12 practice

Count how many times the innermost statement runs as a function of n. Read the method, follow the three worked examples, then try the six questions.

What you should know first

  • Loops

The idea behind counting operations and big-o

Count how many times the innermost statement runs as a function of n. Single loops are O(n), nested loops over n are O(n²), and a loop that halves n each time is O(log n).

Step-by-step method

  1. Count iterations of each loop.
  2. Multiply nested counts.
  3. Keep the fastest-growing term for Big-O.

Worked example 1 (Basic)

for i in range(3 * n): x += 1. How many times does x += 1 run for n = 32, and what is the Big-O?

  1. 3 × 32 = 96
  2. O(n)
  3. Answer: 96; O(n)

Worked example 2 (Standard)

k = n; while k > 1: k = k // 2. How many iterations for n = 1000, and the Big-O?

  1. Halving 1000 until 1
  2. 9 iterations; O(log n)
  3. Answer: 9; O(log n)

Worked example 3 (Challenge)

for i in range(n): for j in range(i, n): ops += 1. Find ops for n = 200 and the Big-O.

  1. n + (n − 1) + … + 1 = n(n + 1)/2 = 20100
  2. O(n²)
  3. Answer: 20100; O(n²)

Common mistakes and misconceptions

  • Calling a halving loop O(n)
  • Keeping constants in Big-O

Practice questions

  1. (Basic) for i in range(5 * n): x += 1. How many times does x += 1 run for n = 500, and what is the Big-O?
  2. (Basic) for i in range(4 * n): x += 1. How many times does x += 1 run for n = 32, and what is the Big-O?
  3. (Standard) k = n; while k > 1: k = k // 2. How many iterations for n = 100, and the Big-O?
  4. (Standard) k = n; while k > 1: k = k // 2. How many iterations for n = 500, and the Big-O?
  5. (Challenge) for i in range(n): for j in range(i, n): ops += 1. Find ops for n = 64 and the Big-O.
  6. (Challenge) for i in range(n): for j in range(i, n): ops += 1. Find ops for n = 100 and the Big-O.

Answer key with full working

  • Q1: 5 × 500 = 2500 → O(n) → Answer: 2500; O(n)
  • Q2: 4 × 32 = 128 → O(n) → Answer: 128; O(n)
  • Q3: Halving 100 until 1 → 6 iterations; O(log n) → Answer: 6; O(log n)
  • Q4: Halving 500 until 1 → 8 iterations; O(log n) → Answer: 8; O(log n)
  • Q5: n + (n − 1) + … + 1 = n(n + 1)/2 = 2080 → O(n²) → Answer: 2080; O(n²)
  • Q6: n + (n − 1) + … + 1 = n(n + 1)/2 = 5050 → O(n²) → Answer: 5050; O(n²)

Syllabus note

This skill is listed under "Algorithm Analysis" for Class 12 in the NCERT/CBSE books. ICSE, IGCSE, IB and state boards may teach it in a different chapter or year.

Answers on this page are generated and automatically re-checked by a second, independent calculation. They have not been reviewed by a teacher — if you spot a problem, tell us on WhatsApp.

Related practice and notes

Frequently asked questions

Which chapter is counting operations and big-o in?

"Algorithm Analysis", Class 12 Computer Science (NCERT/CBSE). Other boards may place it differently.

How were the answers checked?

Answers on this page are generated and automatically re-checked by a second, independent calculation. They have not been reviewed by a teacher — if you spot a problem, tell us on WhatsApp.

Book a free demo class