Contents

## ### Computational Complexity:-

Computational complexity is a field from computer science which analyses algorithms based on the amount resources required for running it.

### time complexity:-

the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.

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.

### best-case:-

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.

### average-case:-

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

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.

### Name                             Time Complexity

Constant Time         –              O(1)
Logarithmic Time    –             O(log n)
Linear Time               –             O(n)
Quasi-linear Time      –            O(n log n)
Exponential Time    –              O(2^n)
Factorial Time         –             O(n!)

Time Complexities:-
Constant Time — O(1)
Logarithmic Time — O(log n)
Linear Time — O(n)
Quasi-linear Time — O(n log 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
x=1        ————-c3
break
if x  :             —————-c4
print (n,”is a prime number”)           ———–c5
else :
print  (n,”is a prime number”)   ———–c6
complexity of program
ans.
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.

i=1       ———–c0
while i<=n:        ————–n
j=1        ———-c1
while j<=n:            ———–n
k=1              ———-c2
while k<=n:            ———n
print(i,j,k)           ———–c3
k=k+1             ————c4
j=j+1                     ———–c5
i=i+1                     ———c6
ans.    o(n3)                           consider the dominant term which is n.

Idea of algorithmic efficiency class 12  important question