Comments on Big-Oh (O) from CLRS
Section 3.1 of CLRS (Cormen, Leiserson, Rivest, Stein) discuss the Big-Oh notation O. The linear function an + b is O(n2), which is easily verified by taking c = a + |b|. cg(n) is a2n + ba + |b|b + |b|an. At the first glance this seems true if a + b >= n, since O is the worst case, we can use this. In addition, a = b = sqrt(n) also help in making the function O(n2). Please see the plots below
Figure 1: Plot of n2
Figure 2: Plot of a = 1,b = n
Figure 3: Plot of a = n,b = 1
Figure 4: Plot of a = sqrt(n),b = sqrt(n)
Figure 5:Plot of a = 1,b = 1
I think it is non-trivial to suggest find out that the function is indeed
O(n2). Comments please!
Thursday, February 10, 2005
Subscribe to:
Post Comments (Atom)
Ranking and Unranking permutations
I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...
-
(Photo from http://content-usa.cricinfo.com/indvaus2008/content/current/player/28114.html) Dravid's dismal form continues in test crick...
-
I've been reading up on Fast Fourier Transform (FFT) from several books on algorithms that I have, TCLR, Tamassia, Sahni, Numerical Rec...
-
The book is almost out there . There is code and selected solutions as well. The book is supposed to be in full colour from what I heard....
No comments:
Post a Comment