2
$\begingroup$

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$,

enter image description here

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: )

enter image description here

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!

$\endgroup$
3
  • $\begingroup$ Are you familiar with binary search? $\endgroup$ May 1 at 8:19
  • $\begingroup$ Of-course, but the thing is - isn't drawing a decision tree for binary-search algorithm a specific decision tree? I know that I need to draw a decision tree for an arbitrary algorithm that solves the problem. $\endgroup$ May 1 at 9:30
  • $\begingroup$ You cannot draw a decision tree for an arbitrary algorithm. You need to come up with a property that every decision tree which solves the search problem satisfies. $\endgroup$ May 1 at 11:52

2 Answers 2

2
$\begingroup$

You haven't really defined your computation model, so here is a suggestion.

The input to the algorithm is a sorted array $A$ of length $n$ and an element $x$.

The output is either a position $i$ such that $A[i] = x$, or $\bot$, which means that $x$ is not in the array.

An algorithm is a decision tree whose leaves are labeled by outputs, and whose interior nodes are labelled by indices $i \in \{1,\ldots,n\}$, and have three children labeled $A[i] < x$, $A[i] = x$, $A[i] > x$.

An algorithm is legal if for any sorted array $A$ and for any $x$, if we traverse the decision tree then we get the correct answer (this can be formalized more carefully).

The running time of the algorithm is the depth of the decision tree (maximal number of edges in any root-to-leaf path).

Every legal algorithm has at least $n + 1$ different leaves, since for any array $A$ whose elements are distinct, we can find $n+1$ inputs for which the only correct outputs are $1,\ldots,n,\bot$.

Since every internal node has fan-out $3$, a decision tree of depth $d$ has at most $3^d$ leaves. Since $3^d \geq n + 1$, we conclude that $d \geq \log_3 (n+1)$.

This is achieved by binary search, up to a constant factor. With more work, we can show that binary search (probably defined) is strictly optimal. This requires an adversary argument.

$\endgroup$
3
  • $\begingroup$ Thank you. I think I haven't fully understood this whole topic of decision-trees and got things mixed up. I learned about it in sort of an informal way in the context of showing that every comparison-based algorithm has a lower bound of $ \Omega(n log n) $ in W.C. and couldn't establish a grip understanding of what a decision-tree really is. You seem to have a firm understanding of the subject, do you have a good book/reference that discusses decision-trees thoroughly and explains really well what they are? I read about it in CLRS but I still feel gaps in my understanding of it. $\endgroup$ May 4 at 10:08
  • $\begingroup$ Unfortunately I’m not aware of any particular source. Perhaps your professor can help? $\endgroup$ May 4 at 10:10
  • $\begingroup$ Ok, I'll ask him and my teacher-assistants. If they wouldn't know I'll manage somehow. $\endgroup$ May 4 at 10:20
0
$\begingroup$

The lower bound can be found as the minimum height of a binary tree holding $n$ leaves. A complete tree has this property and has a logarithmic height.

$\endgroup$
3
  • $\begingroup$ Yes, but why the decision tree of every algorithm which searches for $ x $ in a sorted array $ A $, will have $ n $ leaves? $\endgroup$ May 2 at 22:02
  • $\begingroup$ Well there are $n$ elements in a sorted array, so $n$ decisions in all, out of which you reach one upon searching using the tree. $\endgroup$
    – Rinkesh P
    May 3 at 3:51
  • $\begingroup$ @hazelnut_116: it is not complete at all. I don't think you understood my answer. $\endgroup$ May 3 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.