MHB Solve Induction Problem: cn <= n log2n

  • Thread starter Thread starter nano1
  • Start date Start date
  • Tags Tags
    Induction
AI Thread Summary
The discussion revolves around solving an induction problem related to the number of comparisons, cn, made by a student studying a list of n elements. The user is challenged to prove that cn is less than or equal to n log2n for n >= 2, given specific initial conditions and a recursive relation. There is acknowledgment that the problem may be complex and requires careful application of mathematical induction. An attachment is mentioned that likely contains a solution or guidance on the induction process. The overall goal is to clarify the induction method to establish the inequality for the number of comparisons.
nano1
Messages
8
Reaction score
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 !
 
Last edited:
Physics news on Phys.org
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
 

Attachments

  • MHBdiscrete2.png
    MHBdiscrete2.png
    10.9 KB · Views: 84

Thread 'Value of intuitionistic logic'

I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
View full post »

Thread 'Formal derivation of statement from Peano Arithmetic system'

I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
View full post »

Similar threads

Why is Axiom of Induction Needed as an Axiom? (Peano's Axioms)
Replies
3
Views
5K
MHB Can You Solve This Set Theory and Binary Number Problem?
Replies
1
Views
2K
Differential algebraic equations
Replies
1
Views
4K
Induction Proof - show 2^n = sum of nCi (i = 0 to n)
Replies
4
Views
7K
I Help solving a System of Linear Equations
Replies
5
Views
2K
I How Can I Improve My Method for Translating Points on Coordinate Axes?
Replies
2
Views
2K
Flux and Current of Magnetic Core With Air Gap
Replies
13
Views
4K
What is the equation for f(x) using just a,b,c,d in a geometric series?
Replies
10
Views
3K
Solve Tricky Induction Q: Integral Power of (\sqrt{2}-1)^k
Replies
2
Views
2K
Solving Induction Proof for Positive Integers: Step-by-Step Guide
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top