Computer ScienceISC Class 12 · Complexity and Big O Notation

Time Complexity and Big O Analysis of Algorithms (ISC Class 12 Computer Science)

Q: What is Big O notation?

It describes the upper bound on how the number of steps of an algorithm grows with the input size, keeping only the dominant term, such as O(n) or O(n^2).

Q: Why do we ignore constants in Big O?

Because for large inputs the growth rate matters far more than a fixed multiplier, and constants depend on the machine and the programming language.

Q: What is the difference between O(n) and O(n^2)?

In O(n) the work grows in proportion to n, so doubling n doubles the work; in O(n^2) the work grows with the square, so doubling n makes it four times as large.

Q: Which is faster, binary search or linear search?

Binary search, O(log n) against O(n), but it needs a sorted array.

Updated 17 October 2026 · Draft, not yet fact-checked

Complexity measures how the number of steps an algorithm takes grows with the input size n. Big O notation keeps only the dominant term and drops constants: 3n^2 + 5n + 20 is O(n^2). Common orders from fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n). State best, average and worst cases separately where they differ.

Understand Time Complexity and Big O Analysis of Algorithms

Input size and steps. Complexity is estimated from the input size n (number of elements in an array, digits in a number, discs in Hanoi) and the number of basic steps (comparisons, assignments) as a function of n. It is a count of steps, not seconds, so it does not depend on the machine.

Counting from code.

A single statement, an array access a[i] or an arithmetic operation: constant, O(1).
A loop running n times with constant work inside: O(n).
Two nested loops each running n times: n x n = O(n^2). A triangular nest (j <= i) runs 1 + 2 + ... + n = n(n+1)/2 times, still O(n^2).
A loop that doubles (i *= 2) or halves its counter runs about log2 n times: O(log n).
Loops one after another add; nested loops multiply.

Dominant term and constants. For large n the term with the highest growth rate dominates, and constant multipliers are ignored. T(n) = 3n^2 + 5n + 20 is O(n^2). Big O gives an upper bound on growth.

Best, average and worst case. Linear search: best case 1 comparison (key at the first place), worst case n (key last or absent), average about n / 2. Complexity is usually quoted for the worst case unless stated otherwise.

Complexity of the syllabus algorithms.

Linear search: O(n). Binary search (sorted array): O(log n).
Bubble sort: O(n^2) worst and average; O(n) best if a swap flag stops the passes on sorted data.
Selection sort: O(n^2) in every case (always about n(n-1)/2 comparisons).
Insertion sort: O(n^2) worst and average; O(n) best (already sorted).
Factorial and digit-sum recursion: O(n) and O(log n) calls respectively (number of digits); Tower of Hanoi: O(2^n) moves.
Access of an array element by index (including address calculation): O(1).
Solving a system of n linear equations by elimination: about O(n^3).

Recursion costs extra memory for the call stack as well as time; space can also be analysed in the same way.

Time Complexity and Big O Analysis of Algorithms: key facts

Growth order: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)
Left is the slowest growth
Right is the fastest growth; Smaller is better.
Loop counts: Single loop to n n steps
Nested loops to n and n n^2 steps
Triangular nest n(n + 1)/2 steps
Doubling loop about log2 n steps; Counts become Big O after dropping constants.
Dominant term: Keep the highest-growth term
Drop constant multipliers
3n^2 + 5n + 20 is O(n^2)
n + 100 is O(n); Low-order terms matter little for large n.
Search and sort: Linear search O n
Binary search O log n
Bubble, selection, insertion sort O n^2
Best case of insertion sort O n; Worst case is quoted unless stated.

Single loop to n	n steps
Nested loops to n and n	n^2 steps
Triangular nest	n(n + 1)/2 steps
Doubling loop	about log2 n steps

Linear search O	n
Binary search O	log n
Bubble, selection, insertion sort O	n^2
Best case of insertion sort O	n

How to answer Time Complexity and Big O Analysis of Algorithms questions

Use this routine to find the complexity of a code fragment.

1Choose the input size n and the basic operation to count.
2Count how many times the innermost statement runs as a function of n (multiply nested loops, add separate loops).
3For a doubling or halving loop, count the values taken by the counter to get log2 n.
4Write the exact expression, then keep the dominant term and drop constants.
5State the order as O(...) and the case (best, average or worst) it refers to.
6Check with a small n by actually counting.

Time Complexity and Big O Analysis of Algorithms in real life

The idea, met in an everyday situation. Answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Finding a name in a phone list

Suppose a list of 1024 names is checked one by one from the top, or, when it is sorted, by repeatedly opening the middle.

How many comparisons does each need in the worst case?

Try it first, then show the solutionSolution

One by one: up to 1024.
Halving: 1024 shrinks 1024, 512, ..., 1 in 10 halvings, so at most 11 comparisons.

Answer: About 1024 comparisons against 11.

Memory hook: Halving is powerful: each step discards half.

Growing queues at a counter

Suppose every customer must be compared with every other customer to find duplicates.

What is the order of the work, and how does doubling the number of customers affect it?

Try it first, then show the solutionSolution

Comparing every pair is about n x n steps: O(n^2).
Doubling n makes the work about four times as large.

Answer: O(n^2); the work becomes about four times.

Memory hook: Square growth: double the input, quadruple the work.

Tricks to remember Time Complexity and Big O Analysis of Algorithms

Short memory aids. Say each one aloud once, then use it on a question the same day.

Nested multiplies, sequential adds
Loop inside a loop: multiply the counts; loop after a loop: add them.
Use it when: Counting steps.
Doubling means log
A counter that doubles or halves gives log2 n steps.
Use it when: Binary search, i *= 2 loops.
Keep the biggest, drop the numbers
Biggest term only, no constant multiplier.
Use it when: Writing Big O.
Worst case is the promise
Quote the worst case unless asked otherwise.
Use it when: Best, average, worst questions.

Time Complexity and Big O Analysis of Algorithms: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

Example 1: Dominant term · 1 mark · MCQBoard level

For T(n) = 4n^3 + 2n^2 + 9 the dominant term is
(a) 9 (b) 2n^2 (c) 4n^3 (d) n

Try it first, then show the solutionSolution

For large n the n^3 term grows fastest, so 4n^3 dominates; the Big O is O(n^3).

Answer: (c) 4n^3

Example 2: Triangular nested loop · 3 marks · Short answerHarder board level

Find how many times count++ executes for n = 10 and the Big O:

int count = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        count++;

Try it first, then show the solutionSolution

For i = 1 to n the inner loop runs i times: 1 + 2 + ... + n. (1 mark)
For n = 10 the total is 10 x 11 / 2 = 55. (1 mark)
In general n(n + 1)/2 = n^2/2 + n/2, whose dominant term gives O(n^2). (1 mark)

Answer: 55 executions; O(n^2)

Example 3: Doubling loop · 3 marks · Short answerHarder board level

Count the iterations for n = 64 and for n = 100 and give the Big O:

int c = 0;
for (int i = 1; i < n; i *= 2)
    c++;

Try it first, then show the solutionSolution

n = 64: i takes 1, 2, 4, 8, 16, 32 and then 64, which is not less than 64; so 6 iterations, equal to log2 64. (1 mark)
n = 100: i takes 1, 2, 4, 8, 16, 32, 64 and then 128 stops it; 7 iterations. (1 mark)
The counter doubles each time, so the count grows like log2 n: O(log n). (1 mark)

Answer: 6 and 7 iterations; O(log n)

Example 4: Dominant term and share of total · 3 marks · Short answerHarder board level

An algorithm takes T(n) = 3n^2 + 5n + 20 steps. Find T(100), the share of the n^2 term, and the Big O.

Try it first, then show the solutionSolution

T(100) = 3 x 10000 + 500 + 20 = 30520. (1 mark)
The n^2 term is 30000, which is 30000 / 30520 = 98.3% of the total (to one decimal place). (1 mark)
The dominant term is 3n^2; dropping the constant 3 gives O(n^2). (1 mark)

Answer: T(100) = 30520; the n^2 term is about 98.3%; O(n^2)

Example 5: Case: linear versus binary search · 4 marks · Case-basedHOTS / competency

Suppose a sorted array has n = 1024 elements.
(i) State the best, worst and average (about) number of comparisons for linear search when the key is present. (1.5 marks)
(ii) State the worst-case comparisons for binary search. (1 mark)
(iii) Give the Big O of each and one situation where linear search is the only choice. (1.5 marks)

Try it first, then show the solutionSolution

(i) Best 1, worst 1024, average about (1024 + 1) / 2 = 512.5, roughly 512.
(ii) Each comparison halves the range: 1024, 512, ..., 1 takes 11 comparisons at most.
(iii) Linear search O(n); binary search O(log n). Linear search is the only choice when the array is not sorted.

Answer: (i) 1, 1024, about 512 (ii) 11 (iii) O(n) and O(log n); use linear search for an unsorted array

Where students lose marks in Time Complexity and Big O Analysis of Algorithms

The slips examiners see most often, and what to write instead.

Mistake: Keeping constants and low terms
Big O records growth only.
Wrong working
3n^2 + 5n + 20 is O(3n^2 + 5n)
Right working
3n^2 + 5n + 20 is O(n^2)
Do this: Keep the highest term and drop its constant.
Usually costs: 1 mark
Mistake: Calling a doubling loop O(n)
A counter that doubles takes log2 n steps.
Wrong working
for (i = 1; i < n; i *= 2) is O(n)
Right working
for (i = 1; i < n; i *= 2) is O(log n)
Do this: Count how many doublings reach n.
Usually costs: 1 mark
Mistake: Quoting the best case as the complexity
Complexity is normally the worst case unless stated.
Wrong working
Bubble sort is O(n)
Right working
Bubble sort is O(n^2) (best case O(n) with a flag)
Do this: State the case with the order.
Usually costs: 1 mark

Exam tips

Write the exact count first (for example n(n + 1)/2) and then the Big O.
Name the case (best, average, worst) in every complexity statement.
Use the word "dominant term" when you drop smaller terms.
Check your count with a small n such as 4 or 8.
Remember that complexity depends on the input size n, not on the machine.

Practice questions on Time Complexity and Big O Analysis of Algorithms

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

Q1 · 1 mark · MCQBoard level
The Big O of reading the element a[i] of an array is
(a) O(1) (b) O(n) (c) O(log n) (d) O(n^2)
Hint
Access does not depend on the size.
Answer
(a) O(1)
Q2 · 2 marks · Short answerBoard level
Define best case, average case and worst case complexity, using linear search to illustrate.
Hint
Where can the key be?
Answer
Best case is the input for which the algorithm does the least work (key at the first place: 1 comparison). Worst case needs the most work (key last or absent: n comparisons). Average case is the typical expected work over all inputs, about n / 2 comparisons.
Q3 · 3 marks · Short answerHarder board level
Find the exact number of executions of the statements and the Big O:
```
for (int i = 0; i < n; i++)
    sum += i;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        m++;
```
Give the totals for n = 10.
Hint
The loops are one after the other.
Answer
The first loop runs n times and the nested pair runs n x n times, so the total is n + n^2. For n = 10: 10 + 100 = 110. The dominant term is n^2, so the complexity is O(n^2).
Q4 · 3 marks · Short answerHarder board level
Count the executions of c++ for n = 8 and give the Big O:
```
int c = 0;
for (int i = 1; i <= n; i *= 2)
    for (int j = 1; j <= n; j++)
        c++;
```
Hint
How many values does i take?
Answer
i takes 1, 2, 4, 8, which is 4 values (log2 8 + 1). The inner loop runs 8 times for each, so c = 4 x 8 = 32. The order is n log n, written O(n log n).
Q5 · 4 marks · Case-basedHOTS / competency
A program takes 1 second to process n = 1000 items. Assuming the time is proportional to the number of steps, estimate the time for n = 4000 if the algorithm is (a) O(n), (b) O(n^2), (c) O(log n). Which would you prefer for very large n?
Hint
Compare the step counts for the two sizes.
Answer
(a) Steps grow 4 times: about 4 seconds. (b) Steps grow 4 x 4 = 16 times: about 16 seconds. (c) log2 1000 is about 9.97 and log2 4000 is about 11.97, a ratio of about 1.2: roughly 1.2 seconds. For very large n the O(log n) algorithm grows slowest and is preferred.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1.What is the Big O of binary search?Show answer
O(log n).
2.What is the Big O of selection sort?Show answer
O(n^2) in all cases.
3.What does Big O ignore?Show answer
Constant multipliers and lower-order terms.
4.How many steps does a doubling loop to n take?Show answer
About log2 n.
5.What is the best case of linear search?Show answer
One comparison, key at the first place.
6.What is O(1) called?Show answer
Constant time.

Time Complexity and Big O Analysis of Algorithms: frequently asked questions

What is Big O notation?

It describes the upper bound on how the number of steps of an algorithm grows with the input size, keeping only the dominant term, such as O(n) or O(n^2).

Why do we ignore constants in Big O?

Because for large inputs the growth rate matters far more than a fixed multiplier, and constants depend on the machine and the programming language.

What is the difference between O(n) and O(n^2)?

In O(n) the work grows in proportion to n, so doubling n doubles the work; in O(n^2) the work grows with the square, so doubling n makes it four times as large.

Which is faster, binary search or linear search?

Binary search, O(log n) against O(n), but it needs a sorted array.