Sums, Approximations, and Asymptotics T On the other hand, each of the n2 entries in the product matrix takes about n steps to compute. So the running time is roughly n2.n=n. This answer is certainly less precise, but it was easy to derive and is easy to interpret. For example, we can see that doubling the size of the matrices from n x n to 2n x 2n would increase the ng time from about n to about(2n =8n'--a factor of 8. And, assuming a computer performs billions of operations in a reasonable time(as opposed to millions or trillions), the largest matrices we could handle would be roughly 1000 x 1000. Furthermore, this approximate answer is independent of tiny implementation and hardware details. It remains valid even after you upgrade your computer. So approximate answers are quite attractive. And asymptotic notation allows one to ormulate vague statements like"roughly n"in a very precise way. 3.2 Six Funny-Lookin' Symbols Asymptotic notation involves six weird little symbols oh omega theta little-oh little-omega tilde We'll focus on O, which is the most widely used. The others are about equally popular, except for w, which is the Jar-Jar of the lot Suppose that f and g are functions. Then the statement f(x)=O9(x) means that there exist constants to and c>0 such that f(x)≤c·g(x) for all a>ro. Now this definition is pretty hairy. But what it's trying to say, with all its cryptic little constants, is that f grows no faster than g. a bit more precisely, it says that f is at most a constant times greater than g, except maybe for small values of For example, here's a true statement: 5x+100=O(x) This holds because the left side is only about 5 times larger than the right. Of course, for small values of a (like r = 1)the left side is many times larger than the right, but the definition of o is cleverly designed to sweep aside such inconvenient details Let's work carefully through a sequence of examples involving O in order to better understand this definition Claim 2. 5.2 +100=O(r)Sums, Approximations, and Asymptotics II 9 On the other hand, each of the n2 entries in the product matrix takes about n steps to 2 compute. So the running time is roughly n n = n3 · . This answer is certainly less precise, but it was easy to derive and is easy to interpret. For example, we can see that doubling the size of the matrices from n×n to 2n×2n would increase the running time from about n3 to about (2n)3 = 8n3— a factor of 8. And, assuming a computer performs billions of operations in a reasonable time (as opposed to millions or trillions), the largest matrices we could handle would be roughly 1000 × 1000. Furthermore, this approximate answer is independent of tiny implementation and hardware details. It remains valid even after you upgrade your computer. So approximate answers are quite attractive. And asymptotic notation allows one to formulate vague statements like “roughly n3” in a very precise way. 3.2 Six Funny­Lookin’ Symbols Asymptotic notation involves six weird little symbols: O Ω Θ o ω oh omega theta little­oh little­omega tilde ∼ We’ll focus on O, which is the most widely used. The others are about equally popular, except for ω, which is the Jar­Jar of the lot. Suppose that f and g are functions. Then the statement f(x) = O(g(x)) means that there exist constants x0 and c > 0 such that |f(x)| ≤ c · g(x) for all x > x0. Now this definition is pretty hairy. But what it’s trying to say, with all its cryptic little constants, is that f grows no faster than g. A bit more precisely, it says that f is at most a constant times greater than g, except maybe for small values of x. For example, here’s a true statement: 5x + 100 = O(x) This holds because the left side is only about 5 times larger than the right. Of course, for small values of x (like x = 1) the left side is many times larger than the right, but the definition of O is cleverly designed to sweep aside such inconvenient details. Let’s work carefully through a sequence of examples involving O in order to better understand this definition. Claim 2. 5x + 100 = O(x)