Page 561 - Computer science 868 Class 12
P. 561
Let us assume that the time taken to execute the print statement = t
Number of times the i loop executes = n
For each execution of i loop, number of times the j loop executes = n
Number of times the nested loop executes = n * n
Total time taken to execute the nested loop = t*n*n
2
So, the complexity is O(n ).
3. If.. else block: The time complexity of an if and else statement is calculated by calculating the time taken to execute
each block and then deciding whichever of them is larger.
Let us take linear search as an example.
int position=-1; Assignment statement 1 takes constant time t1
for(int i=0;i<n;i++) Loop executes n times
{ if(array[i]= = searchNo) if statement 1 takes constant time t2
{ position = i; Assignment statement 2 takes constant time t3
break; jump statement takes time t4
}
}
if (position = = -1) if statement 2 takes constant time t5
System.out.println("Not found"); Print statement 1 takes time t6
else
System.out.println(" found in "+ position); Print statement 2 takes time t7
Total time taken if found is = t1 + n*(t2+t3+t4) + t5+t6
Total time taken if not found is = t1 + n*(t2+t3+t4) + t5+t7
Here, the only variable factor is n. So, the complexity of linear search is O(N).
4. Logarithmic complexity: Let us take Binary Search as an example.
int BinarySearch ( int A[], int n, int K)
{
int L=0, Mid, R= n-1;
while (L<=R)
{
Mid = (L +R)/2;
if ( K= =A[Mid] )
return Mid;
else if ( K > A[Mid] )
L = Mid + 1;
else
R = Mid – 1 ;
}
return –1 ;}
In this algorithm, after 1st pass the number of steps becomes n/2. After 2nd pass, it becomes n/4 and so on. If p
p
denotes the total number of steps required, then 2 >= n
Taking log of both sides, p log 2 = log n
So, the complexity of binary search is O(log n).
5. Consecutive statements: A program does not consist of a single loop, or nested loop or if only. Different types of
statements execute one after another in a definite sequence.
559
Computational Complexity and Big O Notation 559

