Welcome to our community

Be a part of something great, join today!

Induction Problem

nano

New member
Nov 7, 2013
8
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 in to 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:

c0 = c1 = 0
c2 = 1
c3 <= 3
cn <= (2cn/2) + (n - 1) if n >= 4

Prove that for any n >= 2 the value cn satisfies the equation cn <= n log2n

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 !
 
Last edited:

johng

Well-known member
MHB Math Helper
Jan 25, 2013
236
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.

MHBdiscrete2.png