Idea of algorithmic efficiency class 12 solution
Computational complexity is a field from computer science which analyses algorithms based on the amount resources required for running it.
the time complexity of an algorithm we may find three cases: best-case, average-case and worst-case.
Suppose we have the following unsorted list [1, 5, 3, 9, 2, 4, 6, 7, 8] and we need to find the index of a value in this list using linear search.
this is the complexity of solving the problem for the best input. In our example, the best case would be to search for the value 1. Since this is the first value of the list, it would be found in the first iteration.
worst-case:- this is the complexity of solving the problem for the worst input of size n. In our example, the worst-case would be to search for the value 8, which is the last element from the list.
Big-O notation, sometimes called “asymptotic notation”, is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
Table of common time complexities
These are the most common time complexities expressed using the Big-O notation:
Name Time Complexity
Constant Time – O(1)
Logarithmic Time – O(log n)
Linear Time – O(n)
Quasi-linear Time – O(n log n)
Quadratic Time – O(n^2)
Exponential Time – O(2^n)
Factorial Time – O(n!)
Constant Time — O(1)
Logarithmic Time — O(log n)
Linear Time — O(n)
Quasi-linear Time — O(n log n)
Quadratic Time — O(n²)
Exponential Time — O(2^n)
Factorial — O(n!)
Q 1. determine the complexity of the program that check if a number n is prime.
n = int (input(“Enter a number:”)) ————–c0
x= 0 —-c1
for i in range (2,n):
if n%i ==0: ——–c2
if x : —————-c4
print (n,”is a prime number”) ———–c5
print (n,”is a prime number”) ———–c6
complexity of program
1. = c0 + c1 + (c2 + c3)n + c4 +c5 + c6
2. = C0 +C1n C0=c0 +c1+c4+c5+c6
3. = o(n) C1=c2+c3
consider the dominant term which is n.
Q 2. what is the worst case complexity of the code fragment having nested loop followed by a single loop.
ans. for i in range(n): n
for j in range(n): n
sequence of statement c0
for k in range(n): n
sequence of statement c1
ans. o(n2 ) consider the dominant term which is n.
Q 3. find complexity of program.
while i<=n: ————–n
while j<=n: ———–n
while k<=n: ———n
ans. o(n3) consider the dominant term which is n.