MHB Solve Induction Problem: cn <= n log2n

[nano1]

Hey I've been given an equality to solve as a bonus question with a strong hint that a like one would appear on my midterm.
However, I am stumped by it, it appears quite complex to me. Any insight into how to solve this would be greatly appreciated!
I'll try to type it as best I can:

A student is studying a list with n elements. The student determines that the number of comparisons c sub n when the list has n elements satisfies the following relation:

c₀ = c₁ = 0
c₂ = 1
c₃ <= 3
c_n <= (2c_n/2) + (n - 1) if n >= 4

Prove that for any n >= 2 the value c_n satisfies the equation c_n <= n log₂n

I think I have to use induction to solve this but the question appears tricky and weirdly worded. Any help would be awesome, thank you !

 

[johng1]

Hi,
The attachment answers your question. The induction is just a little tricky. Presumably, this is the number of comparisons in some algorithm for a list of length n.

View attachment 1715