Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that initially I have $c n$ objects, for some constant $c \in O(1)$, and I have a function $f$ that yields $f(k) = \varepsilon k$, (for $\varepsilon<1$), if $k \in \Omega(\log n)$, otherwise $f(k) = k$. Is it correct to say that after iteratively applying $f$ to $c n$ some $\ell$ times (we can choose $\ell$ as large as we want), the number of remaining objects is in

(a) $o(\log n)$, or can we only say that it is in

(b) $O(\log n)$?

I think (a) must also hold, since if only (b) was true (and not (a)), then the number of remaining objects must be in $\Omega(\log n)$ and we can still apply $f$, right?

share|improve this question

1 Answer 1

up vote 0 down vote accepted

There is always a possibility of ambiguity when using asymptotic notation. When you see $A=O(x)$ and $A$ depends not only on $x$ but also on some other variable $y$, there are two distinct possibilities: "For all $y$, there is a constant $C$ such that $A\le Cx$." and "There is a constant $C$ such that for all $y$, $A\le Cx$." You know that there is an existential quantifier somewhere, but you don't know where it is placed.

Depending on the context, it may or may not be clear which one is implied. If there is an ambiguity, people tend to use formulations like "$A=O(x)$, where the constant in $O$ does not depend on $y$" or avoid asymptotic notation altogether.

In this particular case, the condition $k=\Omega(\log n)$ almost certainly implies that the constant in $\Omega$ does not depend on $k$, otherwise the condition would be equivalent to the trivial condition $k\ne 0$.

With this in mind, we can replace asymptotic notation by its definition: "There exist constants $c$, $\varepsilon$ and $C$ such that for all $n$ and $k$, $f(k)=\varepsilon k$ if $k\ge C \log n$ and $f(k)=k$ otherwise."

This implies that for $k$ big enough, $\varepsilon C \log n\le \lim\limits_{l\to\infty} f^l(k)< C \log n$ and therefore (a) cannot be true.


However there is still a big issue: the "otherwise" condition should mean "$k\notin \Omega(\log n)$", which actually means "for all $C$, there exists a $k$ such that $f(k)=k$ and $k<C \log n$" which is different from what we wrote above. This means we couldn't reverse the order of the "if" clause! Not only that, but if we used an equivalent definition of $\Omega$ that used strict inequalities we would get a different $f$, which makes absolutely no sense. Likewise if we used $\Omega(\log (n+1))$ we would get a different $f$.

This means that the original formulation is very sloppy at best, if not complete nonsense. A rigorous and more general formulation would be: "For all $k$, $f(k)=\varepsilon k$ if $k\ge k_0$ where $k_0=O(\log n)$ and $f(k)=k$ otherwise." (note that we use $O$ and not $\Omega$; it's also possible to use $\Theta$).

This is more general because the threshold below which $f(k)=k$ does not need to be exactly $C \log n$, and we can still prove (b). Note that we can now reverse the order of the clauses, use a different definition of $O$, or a bound such as $O(\log (n+1))$ and we will get the same $f$.

share|improve this answer
    
Thanks for your detailed answer! :) (Sorry I can't vote up yet.) –  somebody Jun 1 '12 at 3:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.