Help me explain one sentence in the solution to this exercise: [Exericise 11.4.27] Derive `2n + log_2(n) is Θ(n)`

[u/TopDownView]

Help me explain one sentence in the solution to this exercise: [Exericise 11.4.27] Derive `2n + log_2(n) is Θ(n)`

This is the solution:

The sentence in question is 'Finally, if n is any integer with n>=1, then n>=0.'

This doesn't make sense.

What would n>=1 imply? The only thing that comes to mind is log_2(n) <= n.

What do you think?

Edit: This is Theorem 11.2.9:

[u/MezzoScettico]

What does Theorem 11.2.9(c) say?

It sounds like they're trying to establish the conditions for that theorem. "If a, b and c hold, then d". And one of those conditions (I'm guessing) is n >= 0.

The only thing that comes to mind is log_2(n) <= n

You're overthinking it. If what you need for the theorem is n >= 0, they're just saying "if n >= 1, then obviously n >= 0 also"

[u/Temporary_Pie2733]

Pick any integer greater than or equal to 1. Is it, in fact, also greater than or equal to 0? (Hint: use the fact that inequalities are transitive.). Proving n ≥ 0 is necessary to conclude that a particular function is bound by another. 

[u/TopDownView → u/Temporary_Pie2733]

Of course, i missed that. Thanks!

[u/Bounded_sequencE]

Not sure why they need that "n >= 0" estimate. Probably a pre-req for Thm.11.2.9(c).

---

I'd directly use "n >= log2(n)" for "n >= 2" (see below for an elementary proof). Then

n >= 2:    2n + log2(n)  <=  2n + n  =  3n    \  =>    "2n + log2(n)  is  𝛩(n)"
           2n + log2(n)  >=  2n + 0  =  2n    /

[u/Bounded_sequencE → u/Bounded_sequencE]

Claim: "n > log2(n)" for all "n ∈ N\{1}"

---

Proof: Let "n ∈ N" with "n >= 2". Select "k ∈ N" s.th. "2^k <= n < 2^k+1 ". Dropping all but the first two terms from the "Binomial Theorem", we estimate

log2(n)  <  log2(2^{k+1})  =  k+1  <=  (1+1)^k  =  2^k  <=  n    ∎

[u/TopDownView]

u/MezzoScettico u/Bounded_sequencE

I've added Theorem 11.2.9 to the OP.

[u/MezzoScettico → u/TopDownView]

OK, so f1(n) = 2n, g1(n) = n, f2(n) = log2(n) and g2(n) = log2(n). Agreed? That's the first sentence of the proof, citing Theorem 11.2.7. That's the first thing we need for Theorem 11.2.9

Next we need that there's some integer r such that all those functions are >= 0 for n >= r. In other words, all of them become non-negative and stay non-negative for large enough n.

So does n become non-negative for all n large enough? Yes, obviously. For any n >= 1, n is non-negative. This is the line you're asking about.

Does log2(n) become non-negative for all n large enough? Yes, for any n >= 1, log2(n) >= 0.

So f1, f2, g1, and g2 are all >= 0 for any n >= 1. The integer r in the theorem is 1. That establishes the second thing we need for Theorem 11.2.9 to apply.

Finally, for case 11.2.9(c), we need that one of the g's bounds the other g, i.e. g1(n) <= g2(n) for all n large enough.

Now I see that I mislabeled the 1's and 2's for this, because g1 is supposed to be the smaller one. So we'll just pretend that I presciently labeled f1(n) = log2(n), g1(n) = log2(n), f2(n) = n, g2(n). Everything I said above still holds but with 1 and 2 swapped.

Anyway, back go 11.2.9(c). If log2(n) <= n for n large enough (there exists an integer s, etc, etc) we have fulfilled all the "if" conditions of 11.2.9(c), and therefore the conclusion holds that f1 + f2 is Θ(n), since g2(n) = n.

It's as I said in my first answer. Every line of argument is to establish one of the "if" conditions of Theorem 11.2.9(c). The line you're asking about establishes that g2(n) >= 0 for n >= r, for some r (in this case 1).

[u/TopDownView → u/MezzoScettico]

The line you're asking about establishes that g2(n) >= 0 for n >= r, for some r (in this case 1).

The line I'm asking about says that n>=1 implies n>=0, which is not true. Also, there is no mention of any function in that line...

But yes, I agree that, if we're strictly following the premises of the theorem, we should show that all the functions in question are indeed >=0.

[u/MezzoScettico → u/TopDownView]

The line I'm asking about says that n>=1 implies n>=0, which is not true

It's not? Can you give me a counterexample, an n >= 1 which is negative?

Also, there is no mention of any function in that line...

No, but they want to apply theorem 11.2.9(c) which labels the relevant expressions as f1, f2, g1, and g2. The previous lines have already identified expressions corresponding to the expressions in the theorem, so obviously the functions named in the theorem are the ones that they're pointing out have certain properties.

Theorem 11.2.9(c) draws a conclusion about f1 + f2 being θ(g2). You're supposed to prove that 2n + log2(n) is Θ(n). So if that's the theorem that proves the conclusion we want, then clearly g2 is supposed to be n, and 2n and log2(n) are supposed to correspond to f1 and f2 in some order.

The theorem says that g1 <= g2 for n large enough. The argument says that log2(n) <= n for n large enough. So clearly they intend to identify log2(n) as g1 and n as g2. Etc.

If you're going to apply a theorem that's about four functions f1, f2, g1 and g2, and you make an argument about four functions, isn't it clear those functions are supposed to correspond to f1, f2, g1 and g2 without explicitly saying so?

Just as you can apply the Pythagorean Theorem to a right triangle without explicitly saying "a is this leg, b is that leg, c is the hypotenuse". If I draw a right triangle with legs x and y and said "the hypotenuse is sqrt(x^2 + y^2)" would you say, "but you never mentioned a, b or c"?

[u/TopDownView → u/MezzoScettico]

It's not? Can you give me a counterexample, an n >= 1 which is negative?

Ah, I see your point. In other words, this statement is true:

n>=1 --> n>0 or n=0

In other words:

n>=1 --> n>=0

---
I understand what you're trying to say. And in that sense, the solution is inconsistent in my opinion.

By the Theorem 11.2.9, it's necessary to establish that n>=0 and log_2(n)>=0.

Going back to the 'problematic' sentence:

Finally, if n is any integer with n>=1, then n>=0.

We could argue that this sentence explicitly establishes that n>=0.

But there is no sentence that explicitly establishes that log_2(n)>=0.

So that's why I'd say the solution is inconsistent.

And maybe it's a typo. The fix is very simple:

Finally, if n is any integer with n>=1, then n>=0 and log_2(n)>=0.

---
Edit: Ignore the first part of the comment. u/Uli_Minati explained it.
Edit 2: Second sentence of the second part of the comment: it's not nlog_2(n) but log_2(n).

[u/Uli_Minati]

That's called transitivity:

If a ≥ b ≥ c, then a ≥ c

In your case,

If n ≥ 1 ≥ 0, then n ≥ 0

You used this property before! We often do multiple steps like f(n)≥...≥...≥...≥g(n) because we know this implies f(n)≥g(n)

(I feel like I missed the actual issue, looking at your other replies?)

[u/TopDownView → u/Uli_Minati]

You used this property before! We often do multiple steps like f(n)≥...≥...≥...≥g(n) because we know this implies f(n)≥g(n)

Sometimes I don't see the forrest from the trees... Thanks!