#ASYMPTOTIC NOTATIONS

Question

An algorithm is made up of 2 modules M1 and M2. If order of M1 is f(n) and M2 is g(n) then
the order of the algorithm is—

a)max(f(n), g(n))                                    (b) min(f(n), g(n))
(c) f(n) + g(n)                                          (d) f(n) * g(n)
i want the explanation how solution is option a

Comments

There are two module and each module are independent to each other and the algorithm are generated by combining these two module only.  
So let's take an example by considering an arbitrary function value in order of n.
So i am taking
Fn = O(n^2) and gn = O(n^3)
Then algorithm = fn + gn
So it will automatically give g(n). Thus (c).

Again, algorithm = max(fn,gn) becuase combination of two module give one algorithm. So, fn + gn = max(fn,gn) asymptoticaly.
So , option (a) as well as (c) are correct

---

Question asked for Order, So only option (A) is correct not option (C).

Answer 1

Well it's O( f(n) * g(n) ) or O( max( f(n), g(n) ) )

There can be three cases possible with f(n) and g(n) -

Case A : f(n) > g(n)

In this case we take O(f(n)) the complexity of the algorithm as g(n) is a lower order term, we drop it.

Case B : f(n) < g(n)

In this case, we take O(g(n)) the complexity of the algorithm as f(n) is a lower order term, we drop it.

Case C : f(n) == g(n)

Time Complexity can be either O(g(n)) or O(f(n)) (which is equal asymptotically).

 

Hence, max(f(n), g(n))

Comments

How can you say that it is fn*gn, suppose fn =n and gn = n^2

Then according to your explanation,

Fn*gn will become (n$^{3}$)...check once again.

@devansh

---

Check your explanation once, apply by taking arbitrary function in your explanation, you could easily  find out the mistakes where  you have made...and change this to comment....

Answer 2

if f(n)=O(a(n))  and  g(n)=O(b(n)) then f(n) + g(n) = O(max (a(n) , b(n)) ) 

example-

for(j=1;j<=n; j++) { 

                          printf(“gate”);

                        }

 for(i=1,i<=n; i++) {

                       for(j=1;j<=n; j++) { 

                          printf(“gate”);

                        }

                    }                 

here 1^st part take O(n) time , second part O(n^2) time

total – O(n)+O(n^2) =O(n^2)

 

if f(n)=O(a(n))  and  g(n)=O(b(n)) then f(n)*g(n) = O( a(n) * b(n) )

example – 

                   for(i=1,i<=n; i++) {

                       for(j=1;j<=n; j++) { 

                          printf(“gate”);

                        }

                    }                 

here for first loop O(n) and for second loop O(n) , so total  O(n)*O(n)=O(n^2)