Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Difference between complexity logn and log(sqrt(n))

considering

log(sqrt(n)) = (1/2)log(n)

And if for asymptotic analysis we don't consider the constant terms so, is O(log(sqrt(n))) is as good as O(log(n))?

As per my understanding log(sqrt(n)) will grow slowly in comparison to log(n) if we increase the size of n. But I am not able understand the glitch in moving power of (1/2) at front? Is it just this that factor 1/2 only slows down the rate?

consider the case when we have log(n*n) represented as 2log(n) , and log(n)?

like image 244
codenamefreak47 Avatar asked May 28 '14 06:05

codenamefreak47


2 Answers

It is the same asymptotically:

O(log(sqrt(n))) = O(log(n^1/2)) = O(1/2 log(n)) = O(log(n))
like image 50
Eugen Martynov Avatar answered Jan 03 '23 20:01

Eugen Martynov


You are right, O(log(sqrt(n))) is the same as O(log(n)) by the reasoning given in your question.

like image 44
Henry Avatar answered Jan 03 '23 20:01

Henry