1

I'm having trouble understanding a small passage in The Structure and Interpretation of Computer Programs, and I'm hoping someone can help me interpret it.

In the book's introduction to Orders of Growth (Big O Stuff--Page 48 in volume 2) the book states:

We say that R(n) (resources required to compute a problem of size n) has order of growth θ(f(n)) if there are positive constants k1 and k2 such that k1f(n) <= R(n) <= k2f(n) for any sufficiently large value of n.

I understand what that means literally, but I'm having trouble getting the point. Can someone unpack it for me?

ebrts
  • 477
  • 4
  • 9
  • It just means if you can find two constant values and multiple f(n) such that it can sandwitch the function you are analyzing for all values, then it is of that order. If you were not able to sandwitch like that for all values, then it would not have been of that order. It is not specific to SICP, it is about how O(n) is defined. You can read more in some algorithm books like Introduction To Algorithms. SICP is more of how computation works book than algorithm book IIRC. Also resources here means Time, Space etc. – Nishant May 13 '16 at 03:50
  • 1
    Possible duplicate of [What is O(...) and how do I calculate it?](http://programmers.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) –  May 19 '16 at 17:41
  • 1
    Please note that my answer on the dupe target addresses Big-Theta. –  May 19 '16 at 17:41
  • @Snowman I really like your other answer, and I'm glad that I got to read it. That said, I don't think that this question should be closed as a duplicate given that it was really the limit notation that was throwing me off here, and that question doesn't address that particular piece as directly – ebrts May 20 '16 at 00:20
  • @ebrts I added some notes about Big-ϴ. Please note it is community wiki, so anyone (including you) is welcome to add your own improvements. –  May 20 '16 at 03:27
  • I'm voting to close this question as off-topic because it's a better fit for http://cs.stackexchange.com. – Jim G. May 27 '16 at 08:14

2 Answers2

2

The short answer is that this is just the definition of an asymptotic limit. We can try a more intuitive construction though:

Let's say we think our algorithm A is linear, so the order of growth is just θ(n). We don't know the coefficient: maybe it actually requires 2.7 "resources" per additional operation on average, so R(n) ≃ 2.7n, but this exact value is hard to determine.

Now, even if we can't easily determine this value of 2.7, we can perhaps determine that it can't be less than 2, and can't be greater than 5. So long as we can demonstrate that 2n <= R(n) <= 5n always holds, we can be happy that the algorithm is indeed linear, without needing to know exactly what the coefficient is.

Conversely, if we can't find any positive lower limit k1 such that k1.n <= R(n) holds for sufficiently large n, our algorithm must actually by sub-linear. For example, there's no positive constant we could choose that would work if R(n) is really logarithmic. Similarly, if R(n) is really quadratic or exponential, no upper bound we choose will stop it shooting off out the top of our inequality.

Visually, R(n) is the usual straight line, and choosing some upper and lower constant bounds gives you two more straight lines - one steeper and one shallower. If your R(n) stays between them as n gets arbitrarily large, it is asymptotically the same "shape" as the linear function. If it's a different "shape", it will eventually fall out the bottom or pop out the top. The same works for logarithmic shape, or exponential shape.

Useless
  • 12,380
  • 2
  • 34
  • 46
0

The three Big-notations are all related to each other:

  • Big-O is an upper bound. so n ∈ O(n), but also n ∈ O(n*n) and any other larger upper bound.
  • Big-Ω is a lower bound. similarly, n ∈ Ω(n), and also n ∈ Ω(1).

Upper and lower bound are corresponding to each other in the obvious way: f ∈ O(g) means g ∈ Ω(f).

  • Big-θ is a stricter bound. Big-θ is simply a more precise bound that is both an upper and a lower bound. So n ∈ θ(n), but not ∈ θ(n*n) and not ∈ θ(1).
Frank
  • 14,407
  • 3
  • 41
  • 66