1

We have the Java method rangeQuery_count(BSTNode,int,int). Given the root of a BST (keys int) and an interval [a,b], this method returns number of keys of the BST belong to the interval.

static int rangeQuery_count(BSTNode v, int a, int b) { //a<=b
   if(v==null) return 0;
   if(v.key < a) return rangeQuery_count(v.right, a, b);
   else if(v.key > b) return rangeQuery_count(v.left, a, b);
   else return 1 + rangeQuery_count(v.right, a, b) + rangeQuery_count(v.left, a, b);
}

I have to determine an asymptotic estimate of the cost of the algorithm in function of the number of nodes n of the BST. I'm just starting to study these topics and I would like to understand how to calculate the cost of a program.

Mark
  • 1,577
  • 16
  • 43

1 Answers1

2

The first thing to recognise is that the cost depends on the particular values of the input parameters, in your case it depends, for instance, on how many nodes in the search tree fall within the interval. The usual simplifying assumption made here is to calculate the worst possible case. In this case, that will be when all of the nodes in the tree lie within the interval. In that case you will always take the final clause of the else as long as v is not null, you will visit each node of the tree once, and if there n nodes in the tree the cost will go up roughly linearly with n.

mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • Thank you! Excuse me but, how do I determine the type of visit that is made on the tree in the algorithm? – Mark Dec 10 '15 at 14:53
  • I don't know what you mean by visit. If you were numbering nodes we could talk about pre-order, post-order, and in-order, but in this case you just check the comparisons, make recursive calls on the children, and then tot up the number of nodes at and below the current node. – mcdowella Dec 10 '15 at 15:57
  • I mean the three types of depth-first traversal: pre-order, in-order, and post-order. In this case the method that algorithm performs? – Mark Dec 10 '15 at 20:31
  • 1
    I guess post-order, because the final sum is calculated in the node after returning from its children, but the difference between the three is only really clear when a numbering sequence is involved which identifies a particular instant - the instant at which a sequence number is assigned to the node. Any recursive tree search will inevitably enter a node, search its children, and exit the node. To distinguish pre-order from post-order you need to know whether you care about the exit or the entrance. – mcdowella Dec 10 '15 at 20:51