3

So I'm struggling with proving (or disproving) the above question. I feel like it is true, but I'm not sure how to show it.

Again, the question is if g(n) is o(f(n)), then f(n) + g(n) is Theta(f(n))

Note, that is a little-o, not a big-o!!!

So far, I've managed to (easily) show that:

g(n) = o(f(n)) -> g(n) < c*f(n)

Then g(n) + f(n) < (c+1)*f(n) -> (g(n) + f(n)) = O(f(n))

However, for showing Big Omega, I'm not sure what to do there.

Am I going about this right?

EDIT: Everyone provided great help, but I could only mark one. THANK YOU.

Wanna-be Coder
  • 169
  • 1
  • 11

3 Answers3

2

One option would be to take the limit of (f(n) + g(n)) / f(n) as n tends toward infinity. If this converges to a finite, nonzero value, then f(n) + g(n) = Θ(f(n)).

Assuming that f(n) is nonzero for sufficiently large n, the above ratio, in the limit, is

(f(n) + g(n)) / f(n)

= f(n) / f(n) + g(n) / f(n)

= 1 + g(n) / f(n).

Therefore, taking the limit as n goes to infinity, the above expression converges to 1 because the ratio goes to zero (this is what it means for g(n) to be o(f(n)).

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Oooh, I like this method a lot...and I'm guessing this works because you know f(n) and g(n) are both nonzero thanks to knowing g(n) is o(f(n))? – Wanna-be Coder Jan 18 '16 at 22:43
  • Oh, and how can we guarantee they are going to approach a limit? We just know one is strictly larger than another. – Wanna-be Coder Jan 18 '16 at 22:51
  • We actually only need f(n) to be nonzero, since it's the only one in the denominator. As for why g(n) / f(n) tends toward zero in the limit, you can actually show using the formal definition of a limit to infinity (the ε-n one) that if g(n) = o(f(n)), then lim g(n) / f(n) = 0 as n tends toward infinity. That explains why that second term disappears. – templatetypedef Jan 19 '16 at 00:51
  • Makes sense. Thank you for your help! – Wanna-be Coder Jan 20 '16 at 02:11
1

So far so good.

For the next step, recall that in the best case, 0 <= g(n); this should get you a lower bound on g(n) + f(n).

comingstorm
  • 25,557
  • 3
  • 43
  • 67
  • Yeah, I considered adding another c*f(n) to both sides since we essentially want the form c1*f(n) < f(n) + g(n) < c2*f(n), but that didn't feel right to do, as then we have additional constants in the middle, like c1*f(n) < (c1+1)f(n) + g(n) < (c1 + c2)*f(n), but that doesn't feel like a valid alteration, as the middle term should look exactly like we want it, right? – Wanna-be Coder Jan 18 '16 at 22:11
  • No, you have `f(n) <= g(n) + f(n)` from the fact the `0 <= g(n)`. Combine that with the inequality you've already got, and you have lower and upper bounds... – comingstorm Jan 18 '16 at 22:41
  • Don't you need some general constant paired with the f(n) on the left hand side though to satisfy the conditions for Theta? – Wanna-be Coder Jan 18 '16 at 22:44
1

Before we begin, lets first state what little-o and Big-Theta notations means:

Little-o notation

Formally, that g(n) = o(f(n)) (or g(n) ∈ o(f(n))) holds for sufficiently large n means that for every positive constant ε there exists a constant N such that

|g(n)| ≤ ε*|f(n)|, for all n > N                                 (+)

From https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation.

Big-Θ notation

h(n) = Θ(f(n)) means there exists positive constants k_1, k_2 and N, such that k_1 · |f(n)| and k_2 · |f(n)| is an upper bound and lower bound on on |h(n)|, respectively, for n > N, i.e.

k_1 · |f(n)| ≤ |h(n)| ≤ k_2 · |f(n)|, for all n > N              (++)

From https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation.

Given: g(n) ∈ o(f(n))

Hence, in our case, for every ε>0 we can find some constant N such that (+), for our functions g(n) and f(n). Hence, for n>N, we have

|g(n)| ≤ ε*|f(n)|, for some ε>0, for all n>N

Choose a constant ε < 1 (recall, the above holds for all ε > 0), 
with accompanied constant N. 
Then the following holds for all n>N

    ε(|g(n)| + |f(n)|) ≤ 2|f(n)| ≤ 2(|g(n)| + |f(n)|) ≤ 4*|f(n)|    (*)

Stripping away the left-most inequality in (*) and dividing by 2, we have:

|f(n)| ≤ |g(n)| + |f(n)| ≤ 2*|f(n)|, n>N                            (**)

We see that this is the very definition Big-Θ notation, as presented in (++), with constants k_1 = 1, k_2 = 2 and h(n) = g(n)+f(n). Hence

(**) => g(n) + f(n) is in Θ(f(n))

Ans we have shown that g(n) ∈ o(f(n)) implies (g(n) + f(n)) ∈ Θ(f(n)).

dfrib
  • 70,367
  • 12
  • 127
  • 192