First Look at the Big O Notation

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 + c² + c³ + . . . . + cⁿ is :

(a). ?(1) if c < 1

(b). ?(n) if c = n

(c). ?(cⁿ) 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 cⁿ 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 rⁿ⁺¹ . This can be written as r * rⁿ and since r is a constant, we can safely assume that g(n) is ?(cⁿ).

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.