nano1
- 8
- 0
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:
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 !
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:
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:
