0
$\begingroup$

There is the following algorithm:

Recursive_Search(A,low,high,k)
1 if low=high 
2    if[low] = k
3       return low;
4    return 0;
5 third = floor((hig+2*low)/3);
6 ind = Recursive_Search(A,low,third);
7 if ind != 0
8    return ind;
9 return Recursive_Search(A,third+1,high);

I know that the cost of the algorithm will be something like $T(n)=T(n/3)+T(2n/3)+1$ and that it will be $O(n)$. But how do I prove that $T(n) \in O(n)$?

Improve this question
$\endgroup$
2
  • $\begingroup$ Try guess-and-check. See also cs.stackexchange.com/a/83650/755. $\endgroup$ Commented Mar 20 at 6:39
  • $\begingroup$ What does $ + 1$ mean here? Why do you state that equality holds? Hint: prove some linear inequality between $T(n)$ and $n$. $\endgroup$ Commented Mar 20 at 8:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.