1. proving

Can someone please explain this to me?

Given f(n)=2n + 3 lg n, g(n)=n, prove that 2n + 3 lg n = Θ(n)

Proof:
2n + 3 lg n ≤ 2n+3n = 5n for all n ≥ 1
Hence, we can take k1 =5, and n1=1, and conclude that f(n)= O(n)
Since 2n + 3 lg n ≥ 2n, for all n ≥ 1,
we can take k2 = 2, and n2=1, and conclude that f(n) = Ω(n)
Therefore, we have 2n + 3 lg n = Θ(n)

2. Hello

Originally Posted by dandeliondream
Can someone please explain this to me?

Given f(n)=2n + 3 lg n, g(n)=n, prove that 2n + 3 lg n = Θ(n)

Proof:
2n + 3 lg n ≤ 2n+3n = 5n for all n ≥ 1

$2n + 3 lg(n) \le 2n +3n = 5n$, because $lg(n) \le n,\ n \ge 1$

Originally Posted by dandeliondream
Hence, we can take k1 =5, and n1=1, and conclude that f(n)= O(n)
You showed that $f(n) = 2n + 3 lg(n) \le 5n$

5n is in O(n), so f(n) is in O(n)

10312381n would be in O(n), too

Originally Posted by dandeliondream
Since 2n + 3 lg n ≥ 2n, for all n ≥ 1,
$ln(n) \ge 0$
Originally Posted by dandeliondream
we can take k2 = 2, and n2=1, and conclude that f(n) = Ω(n)
pretty obvious, because 2n is in Ω(n) and so is f(n)

Originally Posted by dandeliondream
Therefore, we have 2n + 3 lg n = Θ(n)
Originally Posted by dandeliondream
Because f(n) is in O(n) and Ω(n)

Rapha

3. Originally Posted by Rapha
Hello

$2n + 3 lg(n) \le 2n +3n = 5n$, because $lg(n) \le n,\ n \ge 1$
How do I know above is = 5n?

4. Originally Posted by dandeliondream
How do I know above is = 5n?
Do you know that $lg(n) \le n \ \forall n \ge 1$?

That's all you need to know, because

$2n +3\cdot \displaystyle{\underbrace{lg (n)}_{\displaystyle{\le n}}} \le 2n +3\cdot n = 5n$

In the next line

2n + 3 lg n ≥ 2n

it is the same argument

$lg (n) \ge 0 \forall n \ge 1$

So $2n + 3 \displaystyle{\underbrace{lg (n)}_{\displaystyle{\ge 0}}} \ge 2n +0$

5. Originally Posted by Rapha
Do you know that $lg(n) \le n \ \forall n \ge 1$?

That's all you need to know, because

$2n +3\cdot \displaystyle{\underbrace{lg (n)}_{\displaystyle{\le n}}} \le 2n +3\cdot n = 5n$
Thank you for taking time to explain to me.