Complexity and Big O Notation: ISC Class 12 Computer Science

What Complexity and Big O Notation is about

Weightage: CISCE publishes no chapter or unit weightage for ISC Computer Science. Complexity and Big O Notation is part of Section C, 14 of the 2027 syllabus and can be asked anywhere in the 70-mark Paper 1 (Part I compulsory: ten 1-mark items and a 10-mark short-answer question; Part II: two of three 10-mark questions in each of Sections A and B, and two of three 5-mark questions in Section C).Source: CISCE ISC Computer Science (868) syllabus, examination year 2027; latest Paper 1 specimen (2025) and the 2025 board paper

Key concepts

Input size and counting steps

Input size n: the quantity that measures how big a problem instance is: the number of elements in an array, the number of digits in a number, the number of rows of a matrix, the length of a string.

We estimate running time by counting basic operations (comparisons, assignments, arithmetic) as a function of n, rather than measuring seconds, which depend on the computer.

Rules for counting:
1. A simple statement: constant time, 1.
2. A loop running n times with a constant-time body: about n.
3. Nested loops: multiply: an n-loop inside an m-loop gives n × m.
4. Consecutive blocks: add their counts.
5. if-else: take the larger branch (for the worst case).
6. A loop that halves (or doubles) its variable each time: about log2 n iterations.
7. A method call: the cost of the method's body.

Example: for (i = 1 to P) {...} followed by for (j = 1 to P) for (k = 1 to Q) {...} costs P + P × Q steps: O(P + PQ), which is O(PQ) when Q ≥ 1 because the nested part dominates.

Worked example

[2] Count the iterations of the body in: for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) x++; for (int k = 1; k <= n; k++) y++; and give its Big O. (Apply)

Try it first, then show the solutionSolution

1. Nested loops: n × n = n²; following single loop: n; total n² + n - 1 mark.
2. Dominant term n²: O(n²) - 1 mark.

Answer: n² + n iterations, which is O(n²).

Dominant term and constants

As n grows, the fastest-growing term of a cost function overwhelms the others. That term is the dominant term.
Example: T(n) = 3n² + 5n + 20. For n = 1000: 3n² = 3,000,000; 5n = 5,000; 20 = 20. The n² term is over 99.8 per cent of the total, so T(n) is O(n²).

Constants are ignored in Big O: 3n² and n² are both O(n²), and 500n is O(n). Constant factors depend on the machine and on details of coding; Big O describes the growth rate.

Order of common growth rates (slowest to fastest growing):
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n)

For small n a 'worse' order can still be faster (100n beats n² only when n > 100), but for large inputs the order decides.

Worked example

[2] The cost of a method is T(n) = 2n² + 40n + 300 steps. Identify the dominant term, justify your choice using n = 1000, and give the Big O. (Understand)

Try it first, then show the solutionSolution

1. For n = 1000: 2n² = 2,000,000; 40n = 40,000; 300 = 300; total 2,040,300 - 1 mark.
2. 2n² is about 98 per cent of the total and its share keeps growing with n, so it is the dominant term; dropping the constant 2 gives O(n²) - 1 mark.

Answer: The dominant term is 2n², the fastest-growing term (about 98 per cent of the cost at n = 1000 and rising), so T(n) is O(n²); the lower-order terms and the constant 2 are dropped.

Best, average and worst case

For the same input size, the work can depend on the particular data.

• Best case: the input that needs the fewest steps.
• Worst case: the input that needs the most steps (an upper bound; the usual meaning of an algorithm's Big O).
• Average case: the expected steps over all inputs of size n (assuming some distribution).

Linear search of n elements: best 1 comparison (key first) → O(1); worst n (key last or absent) → O(n); average about n / 2 → O(n).
Binary search: best 1 (key in the middle) → O(1); worst and average about log2 n → O(log n).
Bubble sort (simple version): about n² / 2 comparisons always → O(n²); with an early-exit flag the best case on sorted data is n - 1 comparisons → O(n).
Insertion sort: best (already sorted) n - 1 comparisons → O(n); worst (reverse order) about n² / 2 → O(n²).
Selection sort: always about n² / 2 comparisons → O(n²) in every case.

Worked example

[2] State the best-case and worst-case complexity of insertion sort and the input that produces each. (Analyse)

Try it first, then show the solutionSolution

1. Best case O(n): the array is already sorted, so each new element needs one comparison - 1 mark.
2. Worst case O(n²): the array is in reverse order, so every element shifts past all earlier ones - 1 mark.

Answer: Best case O(n) for already sorted data; worst case O(n²) for data in reverse order.

Big O notation

Definition (informal): T(n) is O(f(n)) if, for large enough n, T(n) is at most a constant multiple of f(n). Big O gives an upper bound on growth, usually for the worst case.

Rules for finding Big O:
1. Find the cost as a function of n.
2. Keep only the dominant term.
3. Drop its constant coefficient.

Examples:

Code pattern	Steps	Big O
single statement	1	O(1)
one loop to n	n	O(n)
loop to n, then loop to m	n + m	O(n + m)
loop to n nested in loop to m	n × m	O(nm)
two nested loops to n	n²	O(n²)
three nested loops to n	n³	O(n³)
loop halving n each time	log2 n	O(log n)

Growth demonstrated by counting comparisons:

// Counts basic operations to show how running time grows with input size n.
public class StepCount
{
    static long linearComparisons(int n, int keyIndex)
    {
        long c = 0;
        for (int i = 0; i < n; i++)
        {
            c++;                            // one comparison a[i] == key
            if (i == keyIndex)
                break;
        }
        return c;
    }

    static long binaryComparisons(int n)    // worst case: key absent, larger than all
    {
        long c = 0;
        int lo = 0, hi = n - 1;
        while (lo <= hi)
        {
            c++;
            lo = (lo + hi) / 2 + 1;         // always go right
        }
        return c;
    }

    static long bubbleComparisons(int n)
    {
        long c = 0;
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - 1 - i; j++)
                c++;
        return c;
    }

    static long twoLoops(int p, int q)      // one loop of p, then nested loops p x q
    {
        long c = 0;
        for (int i = 1; i <= p; i++)
            c++;
        for (int j = 1; j <= p; j++)
            for (int k = 1; k <= q; k++)
                c++;
        return c;
    }

    public static void main(String[] args)
    {
        int[] sizes = {10, 100, 1000};
        for (int n : sizes)
        {
            System.out.println("n=" + n
                + "  linear best=" + linearComparisons(n, 0)
                + "  linear worst=" + linearComparisons(n, n - 1)
                + "  binary worst=" + binaryComparisons(n)
                + "  bubble=" + bubbleComparisons(n));
        }
        System.out.println("p=10,q=5: " + twoLoops(10, 5) + "   p=100,q=50: " + twoLoops(100, 50));
    }
}

Output:

n=10  linear best=1  linear worst=10  binary worst=4  bubble=45
n=100  linear best=1  linear worst=100  binary worst=7  bubble=4950
n=1000  linear best=1  linear worst=1000  binary worst=10  bubble=499500
p=10,q=5: 60   p=100,q=50: 5100

Multiplying n by 10 multiplies linear search's worst case by 10, adds only about 3 to binary search, and multiplies bubble sort's comparisons by about 100: O(n), O(log n) and O(n²).

Worked example

[1] Write the Big O of: for (i = 1; i <= n; i++) for (j = n; j > 1; j = j / 2) { ... } (Analyse)

Try it first, then show the solutionSolution

1. The outer loop runs n times; the inner loop halves j each time, so it runs about log2 n times; nested loops multiply: n × log2 n - 1 mark.

Answer: O(n log n).

Complexity of standard algorithms

Algorithm	Best	Average	Worst
Linear search	O(1)	O(n)	O(n)
Binary search (sorted)	O(1)	O(log n)	O(log n)
Bubble sort	O(n) with early exit, else O(n²)	O(n²)	O(n²)
Selection sort	O(n²)	O(n²)	O(n²)
Insertion sort	O(n)	O(n²)	O(n²)
Matrix addition (n × n)	O(n²)	O(n²)	O(n²)
Matrix multiplication (n × n)	O(n³)	O(n³)	O(n³)
Gaussian elimination (n equations)	O(n³)	O(n³)	O(n³)
Stack push or pop, queue insert or delete	O(1)	O(1)	O(1)
Linked list insert at start	O(1)	O(1)	O(1)
Linked list search or insert at end	O(1)	O(n)	O(n)
Recursive factorial or sum of digits	O(n) or O(number of digits)
Tower of Hanoi	O(2^n)	O(2^n)	O(2^n)

Why Gaussian elimination is O(n³): for each of n pivot rows, it updates up to n rows of n entries.
Why binary search is O(log n): each comparison halves the remaining range, so about log2 n halvings reach a single element (10 for 1000 elements, 20 for a million).

Worked example

[2] Why is binary search preferred to linear search for a large sorted array? Use Big O. (Evaluate)

Try it first, then show the solutionSolution

1. Linear search worst case O(n): up to n comparisons (1000 for 1000 elements) - 1 mark.
2. Binary search worst case O(log n): about log2 n comparisons (10 for 1000 elements), so it is far faster as n grows; it needs sorted data - 1 mark.

Answer: Binary search needs O(log n) comparisons (about 10 for 1000 items) against O(n) for linear search (up to 1000), so for large sorted arrays it is far faster.

Complexity and Big O Notation in real life

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

Topics in this chapter

• Time Complexity and Big O Analysis of Algorithms

Complexity and Big O Notation: syntax and key facts

Big O rules

Keep the dominant term; drop constants

3n² + 5n + 20 → O(n²).

Loops

consecutive: add; nested: multiply; halving: log n

O(P + PQ) for one loop then a nested pair.

Growth order

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n)

Slowest to fastest growing.

Searches

Linear O(n); binary O(log n)

Best case O(1) for both.

Simple sorts

Bubble, selection, insertion: O(n²) worst

Insertion best O(n).

Comparisons in bubble sort

n(n - 1)/2

n = 100 → 4950.

How the board asks Complexity and Big O Notation

The question patterns to expect, and the method that works for each.

Tricks to remember Complexity and Big O Notation

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

• Add in sequence, multiply when nested

  Side by side add; one inside another multiply.

  Use it when: Counting loops.

• Halving means log

  If the problem size halves each step, think log n.

  Use it when: Binary search and similar.

• Biggest term wins

  Only the fastest-growing term survives in Big O.

  Use it when: Dominant term.

Complexity and Big O Notation: board-level solved questions

Ordered from board level to HOTS. Cover the solution, write your own, then compare step by step.

Case-study practice (Section D style)

Read the situation, then answer every part. In the board paper this is a 6-mark question split into 2 + 1 + 2 + 1 marks.

Where the marks are

How a typical answer is split into step marks. Show every step: a right final answer alone rarely earns full marks.

Where students lose marks in Complexity and Big O Notation

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

• ✗Mistake: Vague definition of the dominant term

  CISCE examiners' comments, 2024: candidates 'Gave vague explanation of dominant term' and 'Confused worst case complexity with dominant term'.

  ✓Do this: Give a cost function with two or more terms (n² + n), show that n² grows fastest, and conclude O(n²).

  Usually costs: 1-2 marks.

• ✗Mistake: Giving only the final Big O without the parts

  CISCE examiners' comments, 2025: for consecutive and nested loops, candidates 'Gave only the dominant term without explaining complexity of non-nested and nested loops'; the expected answer was O(P) + O(PQ).

  ✓Do this: Write the cost of each block (O(P) for the single loop, O(PQ) for the nested loops), add them, then simplify.

  Usually costs: 1 mark.

• ✗Mistake: Keeping constants or lower-order terms

  Big O drops both; O(3n² + n) is not a simplified answer.

  ✓Do this: Simplify to O(n²).

  Usually costs: 1 mark.

• ✗Mistake: Assuming binary search works on unsorted data

  Its O(log n) guarantee depends on sorted order.

  ✓Do this: State 'sorted data' whenever you recommend binary search.

  Usually costs: 1 mark.

Practice questions on Complexity and Big O Notation

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

1. Q1 · 1 mark · Very short answerBoard level

   What is input size?

   Hint

   Measure of the problem.

   Answer

   The quantity that measures the size of the problem instance, such as the number of elements to be processed.

2. Q2 · 1 mark · Very short answerBoard level

   What is the worst-case complexity of linear search?

   Hint

   Every element.

   Answer

   O(n).

3. Q3 · 1 mark · Very short answerBoard level

   What is the Big O of three nested loops each running n times?

   Hint

   Multiply.

   Answer

   O(n³).

4. Q4 · 1 mark · Very short answerHarder board level

   Which is faster for large n: O(n log n) or O(n²)?

   Hint

   log n grows slowly.

   Answer

   O(n log n).

5. Q5 · 2 marks · Short answerHarder board level

   [2] Give the Big O of: for (i = 0; i < n; i++) for (j = i; j < n; j++) count++; and the exact count for n = 4.

   Hint

   n + (n - 1) + ... + 1.

   Answer

   Count = n(n + 1)/2 = 10 for n = 4; O(n²).

6. Q6 · 2 marks · Short answerHarder board level

   [2] Explain best, average and worst case using binary search.

   Hint

   Middle, typical, absent.

   Answer

   Best case: the key is at the first middle position, 1 comparison, O(1). Worst case: the key is absent or found last, about log2 n + 1 comparisons, O(log n). Average: also about log2 n, O(log n).

7. Q7 · 5 marks · Long answerHOTS / competency

   [5] Find the complexity of a method that, for each of n rows of an n × n matrix, finds the row maximum, and then sorts the n row maxima using selection sort. Show the cost of each part.

   Hint

   n² + n²/2.

   Answer

   Row maxima: n rows × n elements = n² comparisons, O(n²). Selection sort of n values: about n²/2 comparisons, O(n²). Total about 1.5n², which is O(n²).

8. Q8 · 10 marks · Long answerHOTS / competency

   [10] (a) Write a method that counts the pairs (i, j) with i < j in an int array whose sum equals a target, and state its complexity. (b) If the array is first sorted, describe an O(n) two-pointer method for the counting step and give the overall complexity including an O(n²) sort. (c) For {1, 5, 7, 3, 5} and target 10, give the count.

   Hint

   Nested loops versus two pointers.

   Answer

   (a) for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) if (a[i] + a[j] == target) c++; about n(n - 1)/2 checks, O(n²). (b) After sorting, set lo = 0, hi = n - 1; if a[lo] + a[hi] < target lo++, if greater hi--, if equal count and move both (handling duplicates); the scan is O(n), but with an O(n²) simple sort the total is still O(n²). (c) Pairs: (5, 5), (7, 3): count = 2 (checked by running the code).

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. 1.Big O of 3n² + 5n + 20?Show answer

   O(n²).

2. 2.Binary search worst case for 1000 elements?Show answer

   About 10 comparisons (O(log n)).

3. 3.Best case of insertion sort?Show answer

   O(n), for already sorted data.

4. 4.Bubble sort comparisons for n elements?Show answer

   n(n - 1)/2.

5. 5.Complexity of Gaussian elimination?Show answer

   O(n³).

Quick revision checklist

The night before the exam: can you do each of these without looking?

• ☐Complexity = growth of steps with input size n.
• ☐Consecutive: add; nested: multiply; halving: log n.
• ☐Dominant term wins; constants dropped.
• ☐Best / average / worst: linear search O(1) / O(n) / O(n).
• ☐Binary search O(log n); simple sorts O(n²); insertion best O(n).
• ☐Matrix multiplication and Gaussian elimination O(n³); Hanoi O(2^n).
• ☐Order: 1 < log n < n < n log n < n² < n³ < 2^n.

Complexity and Big O Notation: frequently asked questions