Help with Big Omega Proof?

Question

It's hard for me to solve the proof. Where t (n) <= cn ^ 1,6, c is a constant. In general, Big Omega is the opposite of Big O, because it is the best case of scenerio and is looking for a lower bound. Thus, there exist c and n0 such that n> = n0. But I'm not sure how to apply this to the proof and how to manipulate the constants in the equation to find c and n0, and to prove that t (n) is Omega (n ^ 1.6).

t (n) = (n-3logn) ^ 1.6 + 5n ^ 1.5 + 7 Omega (n ^ 1.6)

Can someone give an idea on how to do this? Thanks in advance!

In addition, I do not get any criticism, as was obtained from the comment below, this is not a homework problem, but an example taken from a set of exercises, so it is easier for someone to explain the general concept of this type of problem.

Answer 1

Big-Omega definition: f (n) = Omega (g (n)) if there are constants C and K such that for all n> K f (n)> C * g (n)

In other words, you should be able to say something like this: "I choose C = 5, and now for all n> 1000, f (n)> 5 * g (n), so there."

Look at your problem now.

t(n) = (n-3logn)^1.6 + 5n^1.5 + 7 is Omega(n^1.6)

C * n^1.6 < (n-3logn)^1.6 + 5n^1.5 + 7

Divide by n ^ 1.6

C < ((n-3logn)/n)^1.6 + 5n^-0.1 + 7/n^1.6
C < (1 - 3logn/n)^1.6 + 5n^-0.1 + 7/n^1.6

So, let's look at these three members one by one (of course, this will require more formal proof, but it's simple).

1. (1 - 3logn/n)^1.6 = (1 - 0.smth)^1.6 = (0.smth)^1.6 < 1 for n > 2
2. 5n^-0.1 = 5/n^0.1 = 5/smth greater than 1 < 5 for n > 2
3. 7/n^1.6 = 7/smth large < 1 for n > 2

So we see that for any n> 2 C <1 + 5 + 1 = 7

Now you can say: "I choose C = 7, and for any n> 2, C * n ^ 1.6 <..."