Page 568 - Computer science 868 Class 12
P. 568
3. Define Big ‘O’ notation. State the two factors which determine the complexity of an algorithm. [ISC 2018]
4. What is the worst case complexity of the following code segment:
for(int x = 1; x<=a; x++) [ISC 2016]
{
statements;
}
for(int y = 1; y <= b; y++)
{
for (int z = 1; z <= c; z++)
{
statements;
}
}
How would the complexity change if all the three loops changed to N instead of a, b and c?
5. Determine the complexity of the following code snippet:
a. void push(int n)
{ if(top==size-1)
System.out.println("Stack full.........overflow");
else
a[++top]=n; }
b. void deletebeg(Node start)
{
Node ptr=start;
start=ptr.next;
ptr.next=null;
}
c. int i=1;
do
{
System.out.println(i);
i=i+1;
}while(i<=n);
d. for(int i = 1; i <x ; i++)
{
if(x % i == 0)
{
sumOfFactors = sumOfFactors + i;
}
}
if(x == sumOfFactors)
System.out.println(x + " is a perfect number. " );
else
System.out.println(x + " is not a perfect number. " );
}
Previous Years' Questions
n
2
Compare the two complexities O(n ) and O(2 ) and state which is better and why. [ISC 2019]
Ans. O(n ) is better than O(2 )
2
n
Let us see with the help of an example.
Suppose n = 8
2
2
n = 8 = 64
8
2 = 2 = 256
n
n
2
2
Therefore, the complexity in 2 is higher than n . If n increases, 2 increases much more than n . Therefore, the time complexity is
n
n
2
O(n ) is better than O(2 ).
566566 Touchpad Computer Science-XII

