- #1
kasper_2211
- 13
- 0
Homework Statement
The problem statement is as follows:
Let T be a ordered list(sequence) with N entrys. Prove by induction that, [tex]
j-i< 2^{n} \Rightarrow A(i,j) \leq n[/tex] for all integers i, j, n where [tex]1 \leq i \leq j \leq N [/tex]and [tex] n \geq 0 [/tex]
A(i, j) is the number of steps taken by a certain recursive algorithm (much like Binary search). So for example a call A(1, 12) will take 4 steps to complete, and thus A(1, 12) = 4.
Homework Equations
The Attempt at a Solution
I don't have much of an idea where to start. What i think i should do is assume that the left hand side of the implication is true, and then show the right hand side must also be true. Also, I am thinking that i need another way to define A(i, j). Maybe like an equation or recurrence relation. Right now i only have test's showing me that the algorithm runs in log n time. Really what I am looking for is not a solution to the problem but just a pointer in the right direction, as to how to prove implications like this one. Any help is much appreciated.
P.S. I have done inductive proofs before, but this one seems strange to me.
Last edited: