Page 558 - Computer science 868 Class 12
P. 558
14 COMPUTATIONAL
COMPLEXITY AND BIG O
NOTATION
Learning Objectives
14.1 Time and Space Complexity 14.2 Big O Notation
14.3 Complexity Calculations and Dominant Term 14.4 Best Case, Worst Case and Average Case Complexity
14.5 Analysis of Complexity of Common Algorithms
We live in the modern world today which is controlled by computers and software. Computation is a process of solving
any problem by mathematical or logical methods using software or applications. With so many different apps available
in the market for any kind of computation, it becomes essential to analyse them and choose the best one which suits
our requirement. However, we must also consider that the performance of software is dependent on different system
resources. The most fundamental system resources are processor and memory. For any given system, the software
which utilises less memory and takes less time to execute will be the best chosen one.
Any software is governed by its algorithm. You have learnt about algorithm in previous classes and how to develop it.
The performance of an algorithm is measured by two factors:
1. Effectiveness: The effectiveness of an algorithm is depicted by how accurately it produces a result. In other words,
an algorithm should be correct and must produce the desired output for any given set of input.
2. Efficiency: An efficient algorithm is one which produces accurate result in minimum time using minimum
resources.
Computation involves the process of solving a problem and an algorithm associated with it. Complexity involves the
study of factors like time taken by an algorithm and space utilised to determine the minimum resource requirement.
Complexity is thus the measurement of the performance of an algorithm.
The time taken by an algorithm is the total time taken for executing each step. But number of steps taken is directly
proportional to its input size.
Let us take the simplest example: We want to print ‘n’ natural numbers.
When n=5 then print statement will be executed 5 times. If each execution takes ‘s’ nanoseconds then total time taken
is 5xs nanoseconds. When n is 100, the time taken is 100xs nanoseconds. We can thus conclude that for any given
algorithm, its performance depends on its input size.
556556 Touchpad Computer Science-XII

