Algorithms A and B spend exactly

Algorithms A and B spend exactly TA(n) = 5nlog10n and TB(n) = 25n microseconds, respectively, for a problem of size n. Which algorithm is better in the Big-Oh sense?

(A) Algorithm A
(B) Algorithm B
(C) Both are equivalent
(D) No comparison can be made

Answer: B


Niharika dniharika 17 Sep 2016 10:24 pm

someone explain this

Vivek Vikram Singh vivek14 17 Sep 2016 11:21 pm

A = O(nlogn), B= O(n)

It is very trivial if you know the complexity concepts.


Hradesh hradeshpatel 18 Sep 2016 12:03 am

sir, but answer is given B

Habib Mohammad Khan habibkhan 19 Sep 2016 01:20 pm

In Big Oh notation when we say algorithm A = O(B) , this means that A is asymptotically faster and hence more efficient than B as here we are considering time so less time means more efficient and if A = O(B) , it means that A is asymptotically less value than B and hence less time will be consumed as far as A is concerned.

In this Tb(n) = 25n means O(n) and Ta(n) = 5nlogn means O(nlogn).

Obviously n < nlogn and hence n = O(nlogn)

⇒Tb(n) = O(Ta(n)) 

In other words Tb(n) denotes less time consumption in this case as compared to Ta.Hence Tb is better algo as compared to Ta.

Hence , B is the correct option.