Categories
Class 12

Computational Complexity

ISC 2019: Compare the two complexities O(n2) and O(2n) and state which is better and why.
The O(n2) is a quadratic complexity whereas O(2n) is the exponential complexity. When we compare the two, we find that the O(n2) complexity is better because when the input size increases, O(n2) will take less time than O(2n).

ISC 2018: Define Big ‘O’ notation. State the two factors which determine the complexity of an algorithm.
The Big ‘O’ notation is used to depict an algorithm’s growth rate. It tells us about the change in algorithm’s performance when its input size grows. The two factors that determine the complexity of an algorithm are Time and Space.

ISC 2017: (i) What is the worst case complexity of the following code segment:

for(int x = 1; x <= a; x++){
    statements;
}
for(int y = 1; y <= b; y++){
    for(int z = 1; z <= c; z++){
        statements;
    }
}

O(a) + O(b * c) ⇒ O(a + bc) ⇒ O(bc).

(ii) How would the complexity change if all the three loops went to N instead of a, b and c?
O(N2)

ISC 2015: Define computational complexity. Calculate the complexity using Big ‘O’ notation for the following code segment:

for(int k = 0; k < n; k++)
    s += k;

Computational complexity is the measure of the performance of an algorithm.
The Big ‘O’ notation for the above code is O(n).

ISC 2011: What is Big ‘O’ notation?
The Big ‘O’ notation is used to depict an algorithm’s growth rate. It tells us about the change in algorithm’s performance when its input size grows.

ISC 2010: (i) What is the worst case complexity of the following code segment?

for(int i = 0; i < N; i++){
    Sequence of statements;
}
for(int j = 0; j < M; j++){
    Sequence of statements;
}

O(N) + O(M) ⇒ O(N + M).

(ii) How would the complexity change if the second loop went to N instead of M?
O(2N) ⇒ O(N)

By admin

I am a Computer Science teacher in one of the renowned schools in India. I teach Java programming language to my students, and I maintain a website happycompiler.com

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.