Having trouble solving an inequality I'm a trying to prove a recurrence relation (by substitution)

Celia Lucas

Celia Lucas

Answered question

2022-06-13

Having trouble solving an inequality
I'm a trying to prove a recurrence relation (by substitution) for an algorithm class and I'm shamefully stuck in a rather simple looking inequality.
I need to solve this inequality for constant c:
3 c n 2 + n log 2 n c n
The problem is that I don't know how to deal with the logarithm!
Can anyone could point me in the right direction? Also, are there any good books or tutorials on this simple subject? I just returned to school and I can't remember simple things like this...!

Answer & Explanation

Rebekah Zimmerman

Rebekah Zimmerman

Beginner2022-06-14Added 32 answers

The answer below the line shows the inequality is true, which I assumed is what you wanted as most algorithm problems come down to proving things not algebra. Re-reading your question shows you want to solve for c. Just ignore the log 2 n as anything special and just do the algebra to get c by itself.
3 c n 2 + n log 2 n c n n log 2 n 1 2 c n 2 log 2 n c
For n > 1, log 2 n > 0. So n log 2 n > 0. Hence 3 c n 2 + n log 2 n c n since 3 2 c n 1 c n
Llubanipo

Llubanipo

Beginner2022-06-15Added 9 answers

The LHS is not defined for n ( , 0 ] { 1 }
If n > 1
c 0 log n ( 4 ) = log 2 ( 4 ) log 2 ( n ) = 2 log 2 ( n ) n log 2 ( n ) n c 2 3 c n 2 + n log 2 n c n
For 0 < n < 1: as n tends to 1, c log n ( 4 ) tends to , so one does not want to go there.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?