Answer to Question #271979 in Algorithms for Anu

Question

(i) Identify two problems in each category of the following time complexities and derive the

complexity of these identified problems.

O(n log n), and O(n2).

(ii) Suppose you are given n sets: S1, S2…..Sn.. Each set is having n elements. The problem is

to find whether some pairs of these sets are disjoint, i.e. there are no common elements

in these sets. Write pseudo code and calculate its time complexity.

Answer 1

i)

O(n log n): Comparison sort, Fast Fourier transform

O(n$^2$): Bubble sort, Insertion sort

Comparison sort: you must look at every element which is O(n). For each of those elements you look at, you must find out if its in the right order, which is at best O(log n) (binary search for example). So the net sum becomes O(n log n).

Fast Fourier transform: every sum has $O(1)$ complexity. The number of iterations: $O(n),O(2\cdot\frac{n}{2}),O(4\cdot\frac{4}{n})...$ So, every step has the complexity $O(n)$. We have $log_2n$ steps, so the complexity of algorithm will be $O(nlogn)$.

ii)

Start
Scan ​elements A[n], B[n]
for ​loop initiated i to n
 ​for loop initiated j to n
     ​if(A[i]==B[j])
       ​Set is not not a disjoint
     ​else 
       ​set is disjoint
stop

Time complexity of the code $T(n)=O(n^2)$