Path: utzoo!attcan!uunet!dino!atanasoff!hascall
From: hascall@atanasoff.cs.iastate.edu (John Hascall)
Newsgroups: comp.lang.c
Subject: Re: a tree question
Message-ID: <1384@atanasoff.cs.iastate.edu>
Date: 26 Aug 89 14:26:03 GMT
References: <1074@taurus.BITNET> <207600033@s.cs.uiuc.edu>
Reply-To: hascall@atanasoff.cs.iastate.edu.UUCP (John Hascall)
Organization: Iowa State Univ. Computation Center
Lines: 30

In article <207600033@s.cs.uiuc.edu> mccaugh@s.cs.uiuc.edu writes:
 
}Responding to: gillies@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