Recurrence Relation T(n) = T(3/4 * n) + O(1)

Question

I'm working out the recurrence relation

T(n) = T(3/4 * n) + O(1)

It's coming out to be O(log(n)), but I was told before hand that the solution is O(n). I can't find where I'm going wrong - this looks just like the recurrence relation for binary search. Any suggestions?

Answer 1

Try substituting T(n) = c*n or T(n) = c * log n into the equation and solving. One of the two equations will be solvable.

You can also check your answer by evaluating the function for different values of n.

-- Define T in your preferred language
t n | n <= 1 = 1 | otherwise = t (3/4 * n) + 1

-- If it's O(log n), then T(n)/log(n) should be asymptotically constant
-- If it's O(n), then T(n)/n should be asymptotically constant
check1 n = t n / log n
check2 n = t n / n

print [check1 1e10, check1 1e11, check1 1e12, check1 1e13]
print [check2 1e10, check2 1e11, check2 1e12, check2 1e13]

One of these will converge to a small positive number, the other will go to zero or infinity.

Answer 2

T(n) = T(3/4 * n) + O(1) ...............(1) in above eq. T(3/4 * n) is unknown term if you are asking about the solution of this recurrence, then i want to say that we can solve this eq. using substitution method. in this we have to find out the value of T(3n/4) from main eq. and substitute in the eq. recursively. As this recurrence is depends on recursion. n=3n/4 T(3n/4)=T((3/4)^2 * n)+ c ...............(2) notation O replaced by constant c. now substitute T(3n/4) in (1) T(n)= T((3/4)^2 * n) +2c ................(3) now put n=((3/4)^2 * n) in (1) T((3/4)^2 * n)=T((3/4)^3 * n)+c Substitute T(n)= T((3/4)^3 * n)+3c ...............(4)

After kth step eq. will be T(n)=T((3/4)^k * n)+kc ................(5) at this step n will be 2 or 1(input size) (3/4)^k * n= 1 n=(4/3)^k by taking log on both side. log(n)=k*log(4/3) k=log(n) .............. place value in eq. (5) T(n)=T(1)+log(n) * c ..............(6) T(n)= O(log n)

Answer 3

The answers that are given are not showing the correct way of solving this kind of recurrences. You case is easily solved with a Masters theorem and in your case a=1 and b=4/3. This means that c = logb(a) = 0.

Because your f(n) is a constant, you fall in the second case bucket and where k=0. So the solution is , where c = 0 and k = 0. This means that:

---

O(log(n)) is a correct answer