Prashnikaप्रश्निका
Code
About
Computer ScienceClass 12

Complexity and Big O notation - ISC Class 12 Computer Science Questions with Answers

16 past-paper questions on Complexity and Big O notation from ISC Class 12 Computer Science papers (2026-2017), newest first, in full. Tap "Show answer" under a question to see its answer. The syllabus covers Computational complexity, Input size, Dominant terms and constants, Best, average and worst case and Big O notation.

16questions
7years
2026newest
20262 questions
1 mark · MCQOpen: The worst-case complexity for following code segment is: for (int i = 0; i < p…

Choose the correct option.

The worst-case complexity for following code segment is:
for (int i = 0; i < p; i++)
{
    a += Math.sqrt(i);
}
for (int j = 0; j < q; j++)
{
    b += Math.log(j + 1);
}
  • (a)$O(1)$
  • (b)$O(p \times q)$
  • (c)$O(p^2 + q^2)$
  • (d)$O(p + q)$
Show answer

Answer

Correct option: (d)

Answer: (d) $O(p + q)$ The two for-loops are independent (sequential, not nested): the first runs $p$ times giving $O(p)$, the second runs $q$ times giving $O(q)$. Adding two independent loop complexities gives worst-case complexity $O(p) + O(q) = O(p+q)$.
1 mark · MCQOpen: The worst case complexity for following code segment is: for(int i=1; i<= n…

Choose the correct option.

The worst case complexity for following code segment is:
for(int i=1; i<= n; i++)
{
    for(int j=1; j<= i; j++)
    {
        statement;
    }
}
  • (a)O(n+i)
  • (b)O(n×i)
  • (c)O(n)
  • (d)O(n²)
Show answer

Answer

Correct option: (d)

Answer: (d) O(n²) The outer loop executes n times and for each i, the inner loop executes i times. Total executions = 1 + 2 + ... + n = n(n + 1)/2, which gives worst case complexity O(n²).
20256 questions
1 mark · Short answerOpen: For Big O notation, state the difference between O(n) and O(n²).

Answer the following.

For Big O notation, state the difference between $O(n)$ and $O(n^2)$.
Show answer

Answer

Official answer key
$O(n)$ denotes linear time complexity, where the running time grows directly in proportion to the input size $n$; it is typically produced by a single loop that runs $n$ times. $O(n^2)$ denotes quadratic time complexity, where the running time grows in proportion to the square of $n$; it is typically produced by a nested loop (a loop inside a loop), and so it grows far faster than $O(n)$ as $n$ increases.
1 mark · Short answerOpen: For the given code segment, write Big O notation for worst case complexity. for…

Answer the following.

For the given code segment, write Big O notation for worst case complexity.
for ( int i=1; i<=P; i++)
{ Statements }
for (int j=1; j<=P; ++j)
    for (int k=1; k<=Q; k++)
    { Statements }
Show answer

Answer

Two independent (non-nested) loops each running P times give $O(P)$, and a loop of P nested with a loop of Q gives $O(P \times Q)$. Adding the two, the worst-case complexity is $O(P) + O(P \times Q) = O(P \times Q)$ (the $P \times Q$ term dominates for $P, Q \ge 1$).
1 mark · Short answerOpen: “Finding the greatest common divisor (GCD) of two positive integers results in…

Answer the following question.

“Finding the greatest common divisor (GCD) of two positive integers results in the time complexity of $O(\log N)$ where $N$ is the larger number of two inputs”. Justify the statement.
Show answer

Answer

The GCD (by Euclid's algorithm) is found by repeatedly replacing the larger number with the remainder of dividing it by the smaller one. Each such step reduces the larger number to less than half its previous value within at most two steps, so the number of steps needed is proportional to $\log N$, giving a time complexity of $O(\log N)$.
1 mark · Short answerOpen: Consider the following snippet, calculate the time complexity assuming the code…

Answer the following question.

Consider the following snippet, calculate the time complexity assuming the code compiles successfully.
double m = 1, n = 1; 
for (int i = 0; i < x; i++)  
{ 
    m *= Math.random( ); 
} 
for (int j = 0; j < y; j++)  
{ 
    n *= Math.random( ); 
}
Show answer

Answer

$O(x + y)$, which is linear time complexity, $O(n)$: the two for loops run one after another (not nested), taking $x$ and $y$ steps respectively, so the total number of steps grows linearly with the input sizes.
1 mark · Short answerOpen: For the given code segment, write Big O notation for worst case complexity. int…

Answer the following.

For the given code segment, write Big O notation for worst case complexity.
int i=1, j=1, k=1, p;
while (i <= p)
{
    statements
}
while (j <= p)
{
    while (k <= p)
    {
        statements
    }
}
Show answer

Answer

Checked answer.
$O(n^2)$ The first loop runs $n$ times, giving $O(n)$. The second part is a nested pair of loops: the outer loop runs $n$ times and, for each of its passes, the inner loop runs $n$ times, giving $n \times n$ steps, i.e. $O(n^2)$. Adding the two, $O(n) + O(n^2) = O(n^2)$, because the $n^2$ term dominates. Worst case time complexity = $O(n^2)$ (quadratic).
1 mark · Short answerOpen: A student had written the following method to display “Hello World” four times…

Answer the following question.

A student had written the following method to display “Hello World” four times on the output screen.
void displayMessage( ) 
{ 
    System.out.println("Hello World"); 
    System.out.println("Hello World"); 
    System.out.println("Hello World"); 
    System.out.println("Hello World"); 
}
The student modified the code later to reduce the number of lines in the code.
void displayMessage( ) 
{ 
    int i = 1; 
    while(i <= 4)  
    { 
        System.out.println("Hello World"); 
        i++; 
    } 
}
Compare the above code snippets with respect to the time complexity.
Show answer

Answer

Both versions have the same time complexity, $O(1)$ (constant time): the first has 4 fixed print statements and the while loop also always executes exactly 4 times, so in both cases the number of operations does not depend on any input size and stays constant.
20242 questions
2 marks · Short answerOpen: With the help of an example, briefly explain the dominant term in complexity.

Answer the following.

With the help of an example, briefly explain the dominant term in complexity.
Show answer

Answer

In Big O complexity, when the number of operations of an algorithm is expressed as a sum of terms of different growth rates (e.g. $n^2 + n + 5$), the dominant term is the term that grows fastest as the input size n becomes very large - it dominates the total running time for large n, and all other (lower-order) terms and constants become insignificant in comparison and are dropped when stating the complexity. Example: For the expression $f(n) = n^2 + n + 5$, as n grows large, $n^2$ grows much faster than $n$ or the constant $5$. So $n^2$ is the dominant term, and the complexity of the algorithm is written as $O(n^2)$.
2 marks · Short answerOpen: With the help of an example, briefly explain the constant factor in time…

Answer the following.

With the help of an example, briefly explain the constant factor in time complexity.
Show answer

Answer

In time complexity analysis, the constant factor is a multiplicative coefficient in a term that does not depend on the input size n. Big-O notation ignores constant factors because, as n becomes very large, they do not change the growth rate (order) of the algorithm - only the relative rate at which the running time grows with n matters. Example: An algorithm that performs $5n$ operations and another that performs $3n$ operations for an input of size n are both $O(n)$ - the constants 5 and 3 (the constant factors) are dropped, since both algorithms still grow linearly with n.
20202 questions
2 marks · Short answerOpen: Define Big ‘O’ notation. State the two factors which determine the complexity…

Answer the following in short.

Define Big ‘O’ notation. State the two factors which determine the complexity of an algorithm.
Show answer

Answer

Big 'O' notation is a mathematical notation that describes the limiting behaviour of an algorithm: it gives the upper bound on the growth of the running time (or memory) of the algorithm as a function of the input size $n$ (the worst case), ignoring constants and lower-order terms. The two factors that determine the complexity of an algorithm are: 1. Time complexity: the amount of time (number of basic operations) the algorithm takes, as a function of the input size. 2. Space complexity: the amount of memory the algorithm needs, as a function of the input size.
2 marks · Short answerOpen: State the best case and the worst case complexity for bubble sort algorithm.

Answer the following in short.

State the best case and the worst case complexity for bubble sort algorithm.
Show answer

Answer

Bubble sort: Best case: $O(n)$. This happens when the array is already sorted; the optimised bubble sort makes one pass, finds no swaps and stops. Worst case: $O(n^2)$. This happens when the array is in reverse order; every pass makes swaps and about $n(n-1)/2$ comparisons are needed.
20191 question
2 marks · DifferentiateOpen: Compare the two complexities O(n²) and O(2ⁿ) and state which is better and why.

Differentiate between the following.

Compare the two complexities $O(n^2)$ and $O(2^n)$ and state which is better and why.
Show answer

Answer

$O(n^2)$ is quadratic time complexity: the running time grows in proportion to the square of the input size $n$, typically produced by a nested loop (one loop inside another, both running about $n$ times). $O(2^n)$ is exponential time complexity: the running time doubles for every unit increase in $n$, typically produced by algorithms that try all possible subsets/combinations of the input. $O(n^2)$ is the better (more efficient) complexity, because exponential growth ($2^n$) increases far more rapidly than polynomial growth ($n^2$) as $n$ increases. For even moderately large $n$, $2^n$ becomes astronomically larger than $n^2$, making an $O(2^n)$ algorithm impractical for large inputs, whereas an $O(n^2)$ algorithm remains comparatively usable.
20181 question
2 marks · Short answerOpen: Define Big ‘O’ notation. State the two factors which determine the complexity…

Answer the following.

Define Big ‘O’ notation. State the two factors which determine the complexity of an algorithm.
Show answer

Answer

Big 'O' notation is a mathematical notation used to describe the limiting/asymptotic behaviour of an algorithm - it expresses the upper bound on the growth rate of the running time (or space requirement) of an algorithm as a function of the size of its input (in the worst case), ignoring constant factors and lower-order terms. The two factors that determine the complexity of an algorithm are: 1. Time Complexity - the amount of time (number of basic operations) the algorithm takes to execute, as a function of the input size. 2. Space Complexity - the amount of memory/storage the algorithm requires, as a function of the input size.
20172 questions
1 mark · Short answerOpen: How would the complexity change if all the three loops went to N instead of a…

Answer the following question.

How would the complexity change if all the three loops went to $N$ instead of $a$, $b$ and $c$?
Show the code
for (int x = 1; x <= a; x++)
{
    statements;
}
for (int y = 1; y <= b; y++)
{
    for (int z = 1; z <= c; z++)
    {
        statements;
    }
}
Show answer

Answer

$O(N^2)$ With all loops running to N the complexity becomes $O(N + N \times N) = O(N + N^2)$, and the dominant term $N^2$ gives $O(N^2)$.
1 mark · Short answerOpen: What is the worst case complexity of the code segment?

Answer the following question.

What is the worst case complexity of the code segment?
Show answer

Answer

$O(a + b \times c)$ The first loop runs a times and the nested loops run b x c times; the two segments are sequential, so their costs add.

About Complexity and Big O notation

Complexity and Big O notation is a unit of the ISC Class 12 Computer Science syllabus.

The syllabus lists these topics: Computational complexity, Input size, Dominant terms and constants, Best, average and worst case and Big O notation.

Prashnika has 16 past-paper questions on Complexity and Big O notation, from papers of 2017-2026, asked in 7 different years. By kind: Short answer (13), MCQ (2) and Differentiate (1). They carry between 1 and 2 marks, and most are worth 1 mark.

To practise, use the paper generator, which can build a practice paper from this chapter.

Common questions

What topics are in Complexity and Big O notation in ISC Class 12 Computer Science?

The syllabus lists Computational complexity, Input size, Dominant terms and constants, Best, average and worst case and Big O notation.

How many questions on Complexity and Big O notation are in ISC Class 12 Computer Science past papers?

Prashnika has 16 questions on Complexity and Big O notation, from papers of 2017-2026 (board, specimen, improvement and practice papers together).

What kinds of questions are asked on Complexity and Big O notation?

By kind: Short answer (13), MCQ (2) and Differentiate (1).