Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$?
The answer is $ \Omega(\log n) $ because I was told that $ n $ is the number of leaves in the decision tree and so $ \log n $ will be the height of the tree.
First, without being aware of the fact that we are talking about a sorted array, I drew the tree for performing sequential-search on $A$,
But I got a height of $n$ and not $ \log n $.
Next, noticing the given array is sorted, I thought about drawing a decision tree for binary-search algorithm and I found the following link that draws the tree as I wanted, http://bcs.whfreeman.com/webpub/mathematics/gersting7e/chapter%206/section6-3/problem1/Page7.htm
( Here's an image in case you can't enter the link: )
But my teacher-assistant told me that when we want to show a lower-bound on process, we can show it by drawing a decision-tree for any algorithm that solves the process and not just a specific one. Meaning that we want to bound the decision tree's height for any algorithm that solves the specific problem.
That means, I was wrong in my analysis of having drawn both decision trees since I referred to two specific algorithms ( sequential search and binary search ) that solve the problem and not a general algorithm.
Question: So I wanted to know, how can one draw a decision tree for an arbitrary algorithm that solves the problem of finding $x$ in a sorted array $A$? ( It seems to me that the tree will be extremely algorithm dependent like in the two cases I've brought above and so I'm unable to seeing other wisely how the decision tree can be generalized not for specific algorithms )
Note: The question Doubt in the correctness of decision tree models for constructing a lower bound is similar to mine but not exactly what I asked for since I want to know how the decision tree should look like for any algorithm that solves the described problem.
Thanks in advance for help!