Page 559 - Computer science 868 Class 12
P. 559
14.1 TIME AND SPACE COMPLEXITY
From the above discussions we can derive that complexity depends on two factors:
1. Space complexity: It is the amount of memory space required to run an algorithm. An algorithm which requires the
least memory is considered more efficient.
2. Time complexity: It is the total time taken to execute the instructions (steps) of a program. An algorithm which is
designed using the least number of steps is considered more efficient. However, time complexity is a function of
input size.
The performance of an algorithm is also dependent on several other external factors like:
a. Speed of the computer
b. Size of RAM memory in the computer
c. Operation system running on the device
d. Compiler used for executing the program
14.2 BIG O NOTATION
To analyse complexities and representing them using the mathematical notations, the concept of Asymptotic Notation
is used. ‘Asymptotic’ describes an expression where the value of the variable tends to infinity. This method thus
describes the limiting behaviour of an expression which is useful in representing the running time complexity of the
algorithm.
The different asymptotic notations are:
• Big O Notation (O(n)): It represents the upper bound or the longest time taken by an algorithm to execute, for a
given input size. It is used for calculating the worst case time complexity of an algorithm or the longest time taken
in execution of a program.
• Omega Notation (Ω(n)): It represents the lower bound or the least time taken by an algorithm of given input size
to complete its execution, i.e., it is used for measuring the best case time complexity of an algorithm.
• Theta Notation (Θ(n)): It has the characteristics of both Big O and Omega notations, as it represents the lower and
upper bounds of an algorithm.
The Big O notation measures the growth rate of an algorithm. It determines the change in the performance of an
algorithm with increase in its input size. Big O notation is also used for comparing the performance of two or more
algorithms. Some common Big O notations of an algorithm are shown below.
Big O notation Example
1. O(1) • Pushing or popping an item on the top of a stack
• Inserting an item in rear end or deleting an item from the front end of a queue
• Adding or removing nodes in the front of a linked list
The complexity remains constant as the algorithm is not affected by increase in input size.
2. O(N) • Linear search in an unsorted array
The change in complexity is also linear and is directly proportional to the number of inputs.
If the input size increases or decreases by ‘x’, the growth also changes by ‘x’.
3. O(N ) • Bubble Sort
2
• Selection Sort
• Insertion Sort
The change is quadratic in nature and is directly proportional to the square of the input
size. If the size is n=10, then the number of steps taken is 100. It becomes 400 when the
size changes to 20 and so on.
557
Computational Complexity and Big O Notation 557

