- Thread starter
- #1

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:

c

c

c

c

Prove that for any n >= 2 the value c

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 !

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:

c

_{0}= c_{1}= 0c

_{2}= 1c

_{3}<= 3c

_{n}<= (2c_{n/2}) + (n - 1) if n >= 4Prove that for any n >= 2 the value c

_{n}satisfies the equation c_{n}<= n log_{2}nI 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: