CODEWITHSUNDEEP
big-o
Grez.Kev
Grez.Kev

Reputation: 277

nlogn vs square root of n , Isn't square root slower?

I was doing this quiz on an online course and one question stated;

The function nlogn + √n + 5 may set to belong to
A: nlogn
B: √n
C: n√n

The quiz said the correct answer is A, but isn't square root of n slower? I am new to finding the time complexity of an algorithm and could use an explanation. Or let me know if the answer is wrong.

Upvotes: 4

Views: 12717

Answers (3)

Pacerier
Pacerier

Reputation: 89643

Yes, √n is surely more than logn. (cf)

But you're multiplying that logn with n.

n is obviously more than √n.

(If you would multiply √n with n too, then the answer is n√n.)

Upvotes: 0

Tobi Alafin
Tobi Alafin

Reputation: 249

The correct Hierachy is this:

Superlinear[ n log n] > Linear [n] > sub polynomial [n^(1/a)]

Where a: a >= 1.

Thus n log n = O(n) = O(sqrt(n))

N does not need to be an 'Extremely large number" though Big-Oh deals with limits to infinity. In particular, you can set your n0 as `b+Where b is the base of the logarithm. In this case 10.

Test with n=11 yourself to find out.

Upvotes: 1

Mureinik
Mureinik

Reputation: 311418

You should consider n to be an extremely large number. For any n>2, n>√n and logn>1. Thus, nlogn>√n.

Upvotes: 5

Related Questions