Well, it is the first time I’ve really had a serious look at the big O notation. I actually knew what it was about etc, but I never really delved into it.
I was debating whether I needed to shell out money on a Cormen + Leiserson work but then I came across the penultimate draft of “Algorithms” by Umesh Virkumar Vazirani, Sanjoy Dasgupta and Chris Papadimitriou (how do you pronounce it? ) on Vazirani’s homepage: http://www.cs.berkeley.edu/~vazirani/algorithms.html
I decided to pick the big O notation and after not reading it right the first three times, I finally began to get a hang of things and decided to solve the problems at the end of the big O notation chapter and here is how it went:
Question 1 is boring and simple algebra, so we skip it.
Question 2):
Show that if c is a positive real number, then g(n) = 1 + c + c2 + c3 + . . . . + cn is :
(a). ?(1) if c < 1
(b). ?(n) if c = n
(c). ?(cn) if c > 1
The solution is simple. We know that g(n) is the sum of a geometric sequence. When the common ratio is less than 1, we know that the value of g(n) becomes: 1 / (1 - c). Since this solution has clearly defined bounds, we know that g(n) when c < 1 is ?(1).
Next, when c = 1, we know that every single term is going to be 1 (1 raised to any power is 1). Hence, the computer steps required to approach the solution are:
- (n-1) steps to go from c to cn and list them down as ones.
- 1 step to perform the addition.
The result is ?(n).
The final problem can be solved by observing that:
Here a = 1 and r = c.
It can be observed that 1 - r in the denominator is a constant and can be removed. After carrying out a similar process in the numerator we are left with rn+1 . This can be written as r * rn and since r is a constant, we can safely assume that g(n) is ?(cn).
I actually liked the prologue (believe it or not, this was part of the prologue. I have to get to the first chapter).
Disclaimer: In this post, one image was copied off Wikipedia and the question solved can be found in the penultimate draft of the book, “Algorithms” by Umesh Virkumar Vazirani, C. H. Papadimitriou and Sanjoy Dasgupta.
Enjoy this treat, I am not too sure how much money you need to shell out for the final edition of the book.
3 comments ↓
Of course asymptotic analysis is important and interesting. But I feel the time honoured big-O and little-o notation is stupid. I’m a big fan of Knuth’s, but I’m disappointed that he toes the traditional line here.
Please look at it this way. If f is O(g) and g is O(f), then f and g are asymptotically equivalent. Forget now about big-O and think in terms of this equivalence class (in the standard mathematical sense). Define =, arithmetic operations operations on this class. This way you can do everything in a mathematically crystal clear way and you don’t have to do the black magic with the pitfalls that Knuth warns about.
I’m happy I came across your site, because of your interesting interests. Congratulations on your SAT, which I think is a good test. And congratulations on Purdue.
Instead of putting these little snippets on Twitter, why don’t you try for more substantial pieces. You write well enough for that. Although some blogs are excellent, for myself I’m more ambitious and I only publish essays (vanemden.wordpress.com).
is that vazirani this vazirani? (http://www.cc.gatech.edu/~vazirani/). if so, that dude was my teacher!
but i dropped that class. Honors proofs?…no way.
I think the Vazirani I am talking about is that guy’s brother. Umesh Virkumar Vazirani: http://www.cs.berkeley.edu/~vazirani/
This Vazirani is like the founder of the field of quantum computing (I usually hate calling anyone a founder, but I guess he deserves credit for it courtesy his solid reputation.)
Leave a Comment