HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

small o notation

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
smallnotationstackoverflow

Problem

Let $f$ be an $o(2^{-\sqrt n})$ function, and let $g$ be an $o(2^{-\frac{n}{2}})$ function. Is the function $ f + g - fg$ is an $o(2^{-\sqrt n})$ function?

Can you help me prove that?

I think the answer is correct, but when for example, I consider the expression $\frac{2^{-\sqrt n} + 2^{-\frac{n}{2}} - 2^{-\sqrt n - \frac{n}{2}}}{2^{-\sqrt n}}$, I get something that tends to 1 instead of 0. What am I missing?

Solution

Let's take accordingly $f=2^{-\sqrt n}\varepsilon_1$ and $g=2^{-\frac{n}{2}}\varepsilon_2$, where $\varepsilon_1,\varepsilon_2$ tends to zero. Then you would like to have $f + g - fg = 2^{-\sqrt n} \varepsilon$. So, for $\varepsilon $ we have:
$$\varepsilon = 2^{\sqrt n}\cdot\big(2^{-\sqrt n}\varepsilon_1 + 2^{-\frac{n}{2}}\varepsilon_2 - 2^{-\sqrt n-\frac{n}{2}}\varepsilon_1 \varepsilon_2 \big)\to 0$$
You had missed little-$o$ in your example.

Context

StackExchange Computer Science Q#138306, answer score: 6

Revisions (0)

No revisions yet.