Sequences & Summations

Sequences & Summations

The Growth of Functions Rosen 2.2 Basic Rules of Logarithms If logz (x) = a, then x = za logz (xy) = logz (x) + logz (y) logz (x/y) = logz (x) - logz (y)

logz (xy) = ylogz (x) If x = y then logz (x) = logz (y) If x < y then logz (x) < logz (y) logz (-|x|) is undefined Growth If f is a function from Z or R to R, how can we quantify the rate of growth and compare

rates of growth of different functions? Possible problem: Whether f(n) or g(n) is larger at any point may depend on value of n. For example: n2 > 100n if n > 100 How to quantify growth as n gets bigger? 1200 1000 800 600 400 200

0 -200 0 2 4 6 8 10

12 Big-O Notation Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is O(g(x)) if there are constants CN and kR such that |f(x)| C|g(x)| whenever x > k. We say f(x) is big-oh of g(x). The intuitive meaning is that as x gets large, the values of f(x) are no larger than a constant time the values of g(x), or f(x) is growing no faster than g(x). The supposition is that x gets large, it will approach a simplified limit.

Show that 3x3+2x2+7x+9 is O(x3) Proof: We must show that constants CN and kR such that |3x3+2x2+7x+9| C|x3| whenever x > k. Choose k = 1 then 3x3+2x2+7x+9 3x3+2x3+7x3+9x3 = 21x3 So let C = 21. Then 3x3+2x2+7x+9 21 x3 when x 1. Show that n! is O(nn) Proof: We must show that constants CN and kR such that |n!| C|nn| whenever n >

k. n! = n(n-1)(n-2)(n-3)(3)(2)(1) n(n)(n)(n)(n)(n)(n) n times =nn So choose k = 0 and C = 1 General Rules Multiplication by a constant does not change the rate of growth. If f(n) = kg(n) where k is a constant, then f is O(g) and g is O(f). The above means that there are an infinite number of pairs C,k that satisfy the Big-O definition.

Addition of smaller terms does not change the rate of growth. If f(n) = g(n) + smaller order terms, then f is O(g) and g is O(f). Ex.: f(n) = 4n6 + 3n5 + 100n2 + 2 is O(n6). General Rules (cont.) If f1(x) is O(g1(x)) and f2(x) is O(g2(x)), then f1(x)f2(x) is O(g1(x)g2(x)). Examples: 10xlog2x is O(xlog2x) n!6n3 is O(n!n3) =O(nn+3)

Examples f(x) = 10 is O(1) f(x) = x2 + x + 1 is O(x2) f(x) = 2x5 + 100 x3 + xlogx is O(x5) f(x) = 2n + n10 is O(2n) How would you prove this? Prove that n is O(2 )

10 n Proof: We must show that constants CN and kR such that |n10| C|2n| whenever n > k. Take log2 of both expressions. log22n = nlog22 =n, log2n10 = 10log2n When is 10log2n < n? or n/log2n > 10? 2/1 = 2, 4/2 = 2, 8/3 2.67, 16/4 = 4 32/5 = 6.2, 64/6 10.67

For n = 64, 264 > 6410. So, if we choose then k = 64, C = 1, then |n10| 1*|2n| whenever n > 64. Example: Big-Oh Not Symmetric Order matters in big-oh. Sometimes f is O(g) and g is O(f), but in general big-oh is not symmetric. Consider f(n) = 4n and g(n) = n2. f is O(g). Can we prove that g is O(f)? Formally, constants CN and kR such that |n2| C| 4n| whenever n > k? No. To show this, we must prove that negation is true for all C and k. CN,

kR, n>k such that n2 > C|4n|. CN, kR, n>k such that n2 > 4nC. To prove that negation is true, start with arbitrary C and k. Must show/construct an n>k such that n2 > 4nC Easy to satisfy n > k, then To satisfy n2>4nC, divide both sides by n to get n>4C. Pick n = max(4C+1,k+1), which proves the negation. 10000 9000

8000 7000 n*n 6000 4n 5000 5*4n

4000 10*4*n 3000 20*4*n 2000 1000 0 0

20 40 60 80 100 Is 2n O(n!)? We must show that constants CN and kZ such that |2n| C|n!| whenever n > k.

2n = 2(2)(2)(2)(2)(2) n times n(n-1)(n-2)(3)(2)(1) =n! if n = 4 So let C = 1 and k = 3. Is 2n O(n!)? Note that we could also choose k = 1 and C = 2 Since |20| 2*|0!| = 2 |21| 2*|1!| = 2 |22| 2*|2!| = 4 |23| 2*|3!|= 12

Is f(x)=(x2+1)/(x+1) O(x)? We must show that constants CN and kR such that |f(x)| C|x| whenever x > k. x 2 + 1 x 2 1 + 2 (x 1)(x + 1) + 2 = = = x +1 x +1 x +1 2 x 1 +

When x > 1 (Why?) x +1 Therefore let k=1, C = 1 |(x2+1)/(x+1)| |x| when x > 1 Hierarchy of functions nn nlog n n n 2 n 2

1 n! n2 n3 3 n log2n nn Hierarchy of functions

1 nn nlog n 2 n 2 n3 n! n

3 n n log2n 2 n nn

Hierarchy of functions 1, log2n nn nlog n 2 n2 n3 n! n 3

n n 2n nn Hierarchy of functions 1, log2n, 3n nn nlog n 2 n2 n3

n! n n 2n nn Hierarchy of functions 1, log2n, 3n, n nn nlog n 2

n2 n3 n! n 2n nn Hierarchy of functions 1, log2n, 3n, n, n nn nlog n 2

n2 n3 n! 2n nn Hierarchy of functions 1, log2n, 3n, n, n, nlog2n nn n2 n3

n! 2n nn Hierarchy of functions 1, log2n, 3n, n, n, nlog2n, nn n2 n3 n!

2n nn Hierarchy of functions 1, log2n, 3n, n, n, nlog2n, nn, n2 n! n3 2n nn

Hierarchy of functions 1, log2n, 3n, n, n, nlog2n, nn, n2, n3 n! 2n nn Hierarchy of functions 1, log2n, 3n, n, n, nlog2n, nn, n2, n3, 2n n!

nn Hierarchy of functions 1, log2n, 3n, n, n, nlog2n, nn, n2, n3, 2n, n!, nn Each one is Big-Oh of any function to its right Prove that log10x is O(log2x) First we will prove the following lemma: Lemma: log10x = clog2x where c is a constant. Proof: Let y = log2x. Then 2y = x and log102y = log10x. log102y = ylog102 = log10x. But since y = log2x,

this means that log2xlog102 = log10x. Therefore c = log102 To Prove that log10x is O(log2x) We must show that constants CN and kR such that |log10x| C|log2x| whenever x > k. From the lemma log102log2x = log10x; so choose C = log102, k=0 Prove log(n!) is O(nlogn) We must show that constants CN and kR such that |logn!| C|nlogn| whenever

x > k. We know that n! nn so log(n!) log(nn)= nlogn So choose k = 1, C = 1 Time Complexity We can use Big-O to find the time complexity of algorithms (i.e., how long they take in terms of the number of operations performed). There are two types of complexity normally considered. Worst-case complexity. The largest number of operations needed for a problem of a given size in the worst case. The number of operations that will guarantee a solution.

Average-case complexity. The average number of operations used to solve a problem over all inputs of a given size. Complexity of the Linear Search Algorithm Worst-case complexity The algorithm loops over all the values in a list of n values. At each step, two comparisons are made. One to see whether the end of the loop is reached, and one to compare the search element x with the element in the list. If x is equal to list element ai, then 2i comparisons are made.

If x is not in the list, then 2n comparisons are made. The worst-case complexity is thus 2n and is O(n). Complexity of the Linear Search Algorithm Average-case complexity The algorithm loops over all the values in a list of n values. At each step, two comparisons are again made. On average, the number of comparisons is 2 + 4 + 6 +.+ (2n) n

Whats the numerator? n n(n +1) 2( k= ) 2 k=1 Average case is O(n) Complexity of Pair-wise

Correlation Assume that there are n elements to correlate

Recently Viewed Presentations

  • Vulnerability Analysis of Web-Based Applications

    Vulnerability Analysis of Web-Based Applications

    Vulnerability analysis. web vulnerability analysis - allows one to identify security problems in web-based applications at early stages of development and deployment. Methodologies. Detection model (positive vs. negative) Analysis technique (static vs. dynamic)
  • 1.01 - WordPress.com

    1.01 - WordPress.com

    Time, date, and user identification ... Major OS jobs are to manage physical devices and to present a virtual machine abstraction to applications. For hard disks, the OS provides two abstraction: ... hierarchy beyond primary memory and secondary storage to...
  • Full S.T.2R.E.A.M. Ahead With CLR Manu Platt -

    Full S.T.2R.E.A.M. Ahead With CLR Manu Platt -

    The brain is without doubt our most fascinating organ. Parents, educators, and society as a whole have a tremendous power to shape the wrinkly universe inside each child's head, and with it, the kind of person he or she will...
  • Rhetorical Devices - Alvin Independent School District

    Rhetorical Devices - Alvin Independent School District

    Sometimes an asyndetic list is useful for the strong and direct climactic effect it has, much more emphatic than if a final conjunction were used. ... The multiple conjunctions of the polysyndetic structure call attention to themselves and therefore add...
  • State Fair Famous Americans Created by Mrs. Bowmans

    State Fair Famous Americans Created by Mrs. Bowmans

    Martin Luther King Jr. Born on January 15,1929. The Reverend Martin Luther King, Jr., was the young pastor of a church in Montgomery, Alabama when he was asked to lead the city bus boycott in 1955. In August 1963,King led...
  • Two Racial Revolutionaries: David Walker and George Fitzhugh

    Two Racial Revolutionaries: David Walker and George Fitzhugh

    Two Racial Revolutionaries: David Walker and George Fitzhugh Paradoxes: Racist Abolitionism "Antebellum America thus faced three interrelated paradoxes regarding slavery. First, although many Americans believed slavery was a heinous crime, they simultaneously feared that freeing the slaves would be even...
  • Canada &amp; World War I

    Canada & World War I

    - Old Empire - Young / aggressive - NAVY - ARMY = TENSIONS. 2. another type of nationalism growing in colonized countries: =intense loyalty toward and desire to preserve one's cultural identity, language, traditions Eg. Slavic nations
  • Highlights of Visit to the Rusian Air Force

    Highlights of Visit to the Rusian Air Force

    Highlights of Visit to the Rusian Air Force Museum at Monino By Colonel Tom Whitlock [USAF-Retired] In August of 2005 I made my way to Russia, hungry to see some Russian military aircraft flying at the MAKS airshow.