1

a) $f(n) = O(n^{\log a}-e)$ for some $e>0$

b) $f(n) = \Theta(n^{\log a})$

c) $f(n) = \Omega(n^{\log a}+e)$ for some $e>0$

I think the last is true since limit of $f(n)/g(n)$ is infinity. So $f(n)$ is little omega of $g(n)$. So an $e$ must exist for tight bound. Am I correct? or I am missing something?
First two are incorrect since $lim (f(n)/n^{\log a})$ is infinity, it cannot be $\Theta(n^{\log a})$. Since its $\Omega$, not $\Theta$, it cannot be O.
*All $\log a$ are to the base $b; b>1$.

trickster
  • 39
  • You haven't discussed whether (a) or (b) is true or not. – amWhy Jun 03 '18 at 22:21
  • The first two options are incorrect. Since lim f(n)/n^loga is infinity, therefore it can't be theta of n^loga (for it to be big theta lim f(n)/n^loga should be a constant). Since its big omega, and not big theta it cant be big O. – trickster Jun 03 '18 at 22:28
  • That would look better if it were added in an edit to your post :-) – amWhy Jun 03 '18 at 22:32
  • 1
    I have edited the post. Cheers! – trickster Jun 03 '18 at 22:38
  • @trickster Please recall that if the OP is solved you can evaluate to accept an answer among the given, more details here https://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work – user Jun 22 '18 at 21:12
  • Funny to see how this was asked, commented, "answered", even with an "answer" accepted, all without noting that option (c) is absurd, being stated with a blatant typo. To be fair, the accepted "answer" is also blatantly offtopic, so... – Did Jun 23 '18 at 07:46
  • I recently got my answer evaluated. Just to add the answer is only partially correct. The answer up-voted only holds if k=0 (mistake that I did). We have to consider other cases as well: k<0 and k>0. Hope it helps. – trickster Jun 27 '18 at 04:50
  • Yeah well, the incident could lead you to reconsider your approach to the site in general, and your choice to accept answers you only half understand in particular, don't you think? – Did Jul 03 '18 at 07:32
  • I am no expert in the topic of discussion. If you will read my question you will notice I already suggested an answer (what I believed was correct and indeed is partially correct). So the way I see it unless a better explanation was offered, I was blind folded. – trickster Jul 03 '18 at 21:33
  • @trickster Not sure I am following. The fact remains that you accepted a deficient answer although it had been signalled to you as such. The consequences for you (that you described in your comment from Jun 27) and for the site (a bad answer being accepted does not make for a good "repository of knowledge", as SE wants to establish itself as) are undesirable. (Unrelated: Please use @.) – Did Jul 13 '18 at 17:22

1 Answers1

0

Yes since

$$\frac{n^{\log a}\cdot k \log n}{n^{\log a}}\to \pm \infty$$

the third option is the correct one.

user
  • 154,566