a tree question

[John Hascall]

In article <207600033 at s.cs.uiuc.edu> mccaugh at s.cs.uiuc.edu writes:
 
}Responding to: gillies at m.cs.uiuc.edu 
 
}> One of the easiest trees to implement is the Splay tree, but there is
}> a high overhead 
}> ....O(log n) time.
  
} But if there is such a high overhead, how do you gain such efficiency?


     In typical theoretical computer science fashion: 
    
        1) Ignore the constant factor: O(log n) really is c * log n
	   (notice how it was ignored above).

        2) If someone mentions "1)", fall back to the asymptotic argument:
	   "When n is very large...".  Never mind that n has to be so huge
	   that it would/could never happen in real life.  "See when n
	   is 1E1000 records..."  :-)


        Imagine the following conversation:

	   Boss:  "This sort of student records you wrote is too slow."
	   You:   "But if we had a billion students it would be fast."
	   Boss:  (beats you severely with your keyboard)


John Hascall