Thread: 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)

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

, because

Originally Posted by dandeliondream

•Hence, we can take k1 =5, and n1=1, and conclude that f(n)= O(n)

You showed that

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,

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

Originally Posted by Rapha

Hello


, because

How do I know above is = 5n?

Originally Posted by dandeliondream

How do I know above is = 5n?

Do you know that ?

That's all you need to know, because



In the next line

2n + 3 lg n ≥ 2n

it is the same argument




So

Originally Posted by Rapha

Do you know that ?

That's all you need to know, because

Thank you for taking time to explain to me.