What is the formula to prove algorithm A is O(logN) based on given constraints?

[kasper_2211]

Homework Statement

Given an algorithm A i need to figure out a formula that can be used to prove that the algorithm is O(logN). I will try to avoid the details of the algorithm, since i need help with the math only. I think all you need to know is that A takes two arguments i and j. So you would call it like A(i, j).
It is given that: 1 \leq i \leq j \leq N
Also i have proven by induction that j - i < 2^n \Rightarrow A(i, j) \leq n
And lastly i know that every time the algorithm runs it takes 7 "time units". The last call before the algorithm terminates takes 3 "time units". (This is not too important).

Homework Equations

1 \leq i \leq j \leq N
j - i < 2^n \Rightarrow A(i, j) \leq n

The Attempt at a Solution

I will call A with A(1, N), that is i = 1 and j = N, since that is the worst case.

Lets call the function/formula we are looking for T(N). Then, T(N) = 3+7*A(1, N). Now i need to figure out what i can say about A(1, N). I know that N >= j - i + 1. I also know that A(1, N) will terminate in at most n steps if j - i < 2^n. So I assume that's the case.(do i need to make this assumption?) From my assumption i see that N >= 2^n + 1. Now, N / 2^n >= 1 and n - log2N <= 0. So n <= log2N. Now since i need to look at worst case i choose n = log2N. Then T(N)=3+7*log2N. Now it can be easily proven that the algorithm is O(logN). For example choosing 10 for c and 2 for k. Am i on the right track here at all? Thanks.

P.S. By the way, there are probably some fancy ways to do a problem like this but i need to only use what's given here. Especially i would like to use the fact that j - i < 2^n \Rightarrow A(i, j) \leq n

 

[kasper_2211]

Obviously my "proof" is not correct. Just forget it.