Contents

## ### Q 1. define Big ‘O’ notation. state the two factors which determine the complexity of an algorithm.

ans. Big ‘O’ notation is a particular tool for assessing algorithm efficieny. it describes the performance or complexity of an algorithm denoted via Big O, e.g.,O(1), O(N),O(N log N) etc.

### Q 2. distinguish between worst-case and best case complexity of an algorithm. ans. the worst- case complexity of the algorithm is the function defined by the maximum number of steps taken on any instance of size n. it represents the curve passing through the highest point of each column.

the best -case complexity of the algorithm is the function defined by the minimum number of steps taken on any instance of size n. it represents the curve passing through the lowest point of each column.

### Q 3. (i) give the meaning of the following common expression in Big O notation: O(N);    O(N2) (ii) list any two  cases to analyse algorithm complexities.

#### ans. (i) O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.

O(N2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set.this is with algorithms that involve nested iterations over the data set.

### Q 4. what is the worst case complexity of following code fragment. for i in range(n): a=i+(i+1) print(a) for j in range(m): b=i*(i+!) print(b)

ans. time taken in execution of given code:
n—        for i in range(n):
a=i+(i+1)         time taken c0
print(a)           ———-c1
m—        for j in range(m):
b=i*(i+!)         ———–c2
print(b)          ———–c3
total time taken  =  n*(c0+c1)+m*(c2+c3)
= nC1+mC2                     [C1=c0+c1,C2=c2+c3]
= O(n+m)

### Q 5. what is the worst-case complexity of the following code fragment having a nested loop followed by a single loop: for i in range(n): for j in range(n): sequence of statements for k in range(n): sequence of statements

ans.
n         for i in range(n):
n                 for j in range(n):
sequence of statements        ———c0
n          for k in range(n):
sequence of statements          ———c1
total time taken  = n*(n+c0)+nc1
=c0n2 + c1n
=O(n2)        [considered the dominant term only]

### Q 6.(a)what is the worst case complexity of the following code fragment. for x in range(a): statements for y in range(b): for z in range(c): statements (b)how would the complexity change if all the three loops repeated N times instead of a,b and c times respectively.

ans. assuming that each statement has O(1) complexity,then:
(a) O(a+bc)       (b)O(n2)

### Q 7. reorder the following efficiencies from the smallest to largest: (a) 2n      (b) n!     (c) n5       (d) 10,000   (e) nlog2(n

ans. 10,000 < nlog2(n) < n5 < 2n < n!

### Q8.reorder the following efficiencies from the smallest to largest: (a) nlog2(n)           (b) n+n2+n3     (c) 24       (d) n0.5

ans.   24  <   n0.5  <  nlog2(n)  <   n+n2+n3

### Q 9. calculate the run time efficiency of following program segment. i=1 while i<=n: j=1 while k<=n: print(i,j,k) k=k+1 j=j+1 i=i+1

ans. there are three nested loops,each loop is executed in n times,so run-time efficiency is
n x n x n = n3
(idea of algorithmic efficiency important questions)

### Q 10. what do you mean by average case.

ans. average-case:- this is the average complexity of solving the problem. This complexity is defined with respect to the distribution of the values in the input data.