home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1926 < prev    next >
Encoding:
Internet Message Format  |  1992-09-15  |  2.0 KB
  1. Path: sparky!uunet!gatech!concert!duke!ola
  2. From: ola@duke.cs.duke.edu (Owen L. Astrachan)
  3. Newsgroups: comp.theory
  4. Subject: big-O, big-Theta
  5. Keywords: asymptotic analysis
  6. Message-ID: <716574072@mantis.cs.duke.edu>
  7. Date: 15 Sep 92 16:21:14 GMT
  8. Organization: Duke University Computer Science Dept.; Durham, N.C.
  9. Lines: 49
  10.  
  11.  
  12. Texts aimed at students in introductory courses most often use big-O
  13. notation exclusively, no mention is made of Omega or Theta.  Often an
  14. informal definition of big-O is given, one that emphasizes "throwing out
  15. constants and ignoring all but the leading term in a polynomial
  16. expression".
  17.  
  18. For example, in Hopcroft and Ullman's _Foundations of Computer Science_
  19. there is a substantial section on big-O including using big-O to give
  20. "tight big-O bounds".  In Cormen/Leiserson/Rivest 's _Algorithms_ we see
  21.  
  22.    " Many people continue to use the O-notation where the $\Theta$-notation
  23.      is more technically precise."
  24.  
  25. I'm interested in whether there is a consensus as to the correct
  26. approach.  The Advanced Placement Computer Science exam is revising it's
  27. curricular guidelines and using something perceived as anachronistic is
  28. not our most fervid desire.  We run into trouble when we have multiple
  29. choice questions since we must do things like:
  30.  
  31.  
  32.       < code or algorithm description >
  33.  
  34. which of the following is the best description of the runtime of the ___
  35. above?
  36.  
  37. (A)  O(log n)
  38. (B)  O(n)
  39. (C)  O(n log n)
  40. (D)  O(n^2)
  41. (E)  O(n^2 log n)
  42.  
  43. Note that we can't say "which of the following is correct", because
  44. picking the largest expression always works.  Using Theta could
  45. alleviate some of these problems, but it would go against the practice
  46. employed in most intro books aimed at programming courses but which
  47. sometimes include informal asymptotic analysis.
  48.  
  49. ----
  50.  
  51. Thanks for any help, opinions, advice.  I'd prefer email responses, I'll
  52. summarize to this group if there's interest.
  53.  
  54. Owen
  55.  
  56. Owen L. Astrachan               internet: ola@cs.duke.edu
  57. Dept.of Computer Science        Phone (919) 660-6522
  58. Duke University                 fax (919) 660-6519
  59. Durham NC 27706
  60.