1

given time complexity

I have to arrange the above time complexity function in increasing order of asymptotic complexity and indicate if there exist functions that belong to the same order.

So, my answer is

$[lg(n)]^2$
$lg(2^n)$ and $log(2^n)$ and $2^{lg(n)}$ these belong to the same order of O(n)
$nlog(n) + 1000 $
$n^{1.1}$

Just wish to check whether i'm right, since I'm not getting the same result as others. Thanks.

hmakholm left over Monica
  • 286,031
LeonBrain
  • 159
  • 1
  • 6

1 Answers1

1

I am familiar with the question. (I am one of the "others") I believe you neglected to specify that lg is log base 2.

In increasing order of asymptotic complexity:

$lg^2(n) = O(lg^2(n))$

$lg(2^n) = n = O(n)$

$log(2^n) = n * log(2) = O(n)$

$2^{lg(n)} = n = O(n)$

$n*log(n)+1000 = O(n log(n))$

$n^{1.1} = O(n^{1.1})$

Dois
  • 126
  • Um, does that differ from the OP's result? – hmakholm left over Monica Nov 19 '14 at 13:20
  • A solution was posted by our student organisation that was different and that's where the confusion was coming from... but that's settled now, unless of course this is actually wrong and someone here corrects this answer. – Dois Nov 19 '14 at 16:12