0

I'm struggling with asymptotic notation a little bit...

As $k$ becomes large, are these two inequalities actually the same?

$k \le n^{\log (n+1) - 1}(1+o(1))$ and $k \le n^{\log (n)}(1+o(1))$?

the first one is better, but it makes no difference since log(n) is asymptotic to log(n+1)-1?

user163833
  • 9

1 Answers1

2

The expression on the LHS can be rewritten as $$ n^{\log (n+1) -1} = n^{\log n -1 + \log (1+\frac{1}{n})} \sim n^{\log n -1} n^{\frac{1}{n}} $$ The second term converges to 1 as $n \to \infty$, but the ratio $\frac{n^{\log n} }{n^{\log n -1}} = n^{\log n -\log n +1} = n$ which diverges to infinity.

Alex
  • 19,262
  • Many thanks. So you're saying that the first inequality is better? Would you mind kindly explaining why $n^{\log n -1 + \log (1+\frac{1}{n})} \sim n^{\log n -1} n^{\frac{1}{n}} $? – user163833 Jul 11 '14 at 12:58
  • If the first function if $f_1(n)$ and the second $f_2(n)$, then $f_1(n) = o (f_2(n))$ or vice versa $f_2(n) = \omega(f_1(n))$. – Alex Jul 11 '14 at 13:02
  • I see, so the 1+o(1) stuff isn't relevant, really? The point is, since the $f_1(n)$ grows so much slower, it's a better inequality?

    I guess this is kinda like comparing $n^{n}(1+o(1))$ with $n^{n-1}(1+o(1))$. Even though n and n-1 are basically the same, these two inequalities are not the same because we're talking about powers of n, right?

     – user163833 Jul 11 '14 at 13:05
  • 'better' for what purpose? – Alex Jul 11 '14 at 13:05
  • I mean better in the sense that it's a stricter inequality for k? – user163833 Jul 11 '14 at 13:07
  • It depends on what $k$ is. If it's some function $k(n)$, it may be $O(f_1)$ or $o(f_1)$, then it's automatically $o(1)$ because $f_1 = o(f_2)$ – Alex Jul 11 '14 at 13:08
  • Sorry for not understanding this. I have two different inequalities. Inequality 1: $k \le n^{\log (n+1) - 1}(1+o(1))$ and inequality 2: $k \le n^{\log (n)}(1+o(1))$? Is any inequality stronger than the other? Are you saying the answer depends on k? – user163833 Jul 11 '14 at 13:11
  • I think k is just some number which grows however it likes, I don't think it's a function of n. Basically, if one wanted to prove one of these, you may as well prove the first inequality? – user163833 Jul 11 '14 at 13:12
  • 'k is just some number which grows however it likes' sounds quite ridiculous. If it's it constant it's just $O(1)$ then. If it 'grows however it likes' asymptotic analysis is useless. To say something about the order of growth, it must be a function of $n$. – Alex Jul 11 '14 at 13:15
  • If your ultimate question is 'which of two functions grows slower', I already answered it. – Alex Jul 11 '14 at 13:15
  • Apologies Alex. In the 6th comment in this discussion did you mean "... it's automatically $o(f_2)$.." instead of "$o(1)$"? – user163833 Jul 11 '14 at 13:19
  • yes, it should be $o(f_2)$. – Alex Jul 11 '14 at 13:26
  • Sorry for being stupid. You're right right. I appreciate you being patient with me. – user163833 Jul 11 '14 at 13:28
  • no problem, you're welcome. – Alex Jul 11 '14 at 13:33
  • Sorry Alex, what if we assume n = o(k) ? Are the two inequalities equivalent in this case, then? – user163833 Jul 15 '14 at 14:08
  • I'm sorry what you are saying makes absolutely no sense. What do you mean by $n = o(k)$? – Alex Jul 15 '14 at 16:07
  • I mean, what if we're saying "k is large" and all we know is that n=o(k)? I feel like I'm saying a lot of things that are stupid? What exactly am I saying that's wrong? – user163833 Jul 15 '14 at 16:12