patternMinor
small o notation
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?
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.
$$\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.