Page 107 - Computer science 868 Class 12
P. 107
While judging the performance of an algorithm, it is important to calculate the total time taken for its execution and
it has been observed that the time changes with the change in the input size. Thus, it is necessary to analyse how
the time increases or decreases with an increase or decrease in input size. This comparison of the performance of an
algorithm can be done using Big O notation.
Definition
Big O notation is a measurement of growth rate of an algorithm with increase in its input size. It defines the upper
bound of an algorithm or the maximum time taken by an algorithm for a given input size.
While calculating Big O notation, the following three cases may arise:
• Best case complexity: For any input of size ‘n’, the function takes the minimum time or the minimum number of
steps for execution. It defines the lower bound of an algorithm.
• Worst case complexity: For any input of size ‘n’, the function takes the maximum time or the maximum number of
steps for execution. It defines the upper bound of an algorithm.
• Average case complexity: In the average case analysis, we take all the possible inputs combination and calculate
their individual computation time and then calculate the average of all the data. So, average case complexity
calculates the average time taken by an algorithm for execution.
3.5 SOME STANDARD ALGORITHMS
3.5.1 Algorithm Involving Decision Making Statements
Problem 1: Write an algorithm to enter marks of a student and print grade as follows:
Marks Grade
upto 90 A
89 to 75 B
74 to 60 C
Below 60 D
Step 1: Start.
Step 2: Accept marks in m.
Step 3: If m>=90 then print ‘Grade A’, go to Step 7.
Step 4: If m>=75 then print ‘Grade B’, go to Step 7.
Step 5: If m>=60 then print ‘Grade C’, go to Step 7.
Step 6: Print ‘Grade D’.
Step 7: Stop.
2
Problem 2: Write an algorithm to find the roots of a quadratic equation. For any quadratic equation ax +bx+c=0 the
roots are calculated as:
4
-b ± b 2 - a c
a 2
Step 1: Start.
Step 2: Accept coefficients a, b and c.
105
Implementation of Algorithms to Solve Problems 105

