CSCI 2610 - Discrete Mathematics

CSCI 2610 - Discrete Mathematics

Discrete Mathematics CS 2610 February 26, 2009 -- part 1 Big-O Notation Big-O notation is used to express the time complexity of an algorithm We can assume that any operation requires the same amount of time.

The time complexity of an algorithm can be described independently of the software and hardware used to implement the algorithm. 2 Big-O Notation Def.: Let f , g be functions with domain R0 or N and codomain R. f(x) is O(g(x)) if there are constants C and k st x > k, |f (x )| C |g (x )| f (x ) is asymptotically dominated by g (x ) C|g(x)| is an upper bound of f(x).

C and k are called witnesses to the relationship between f & g. C|g(x)| |f(x)| k 3 Big-O Notation To prove that a function f(x) is O(g(x))

Find values for k and C, not necessarily the smallest one, larger values also work!! It is sufficient to find a certain k and C that works In many cases, for all x 0, if f(x) 0 then |f(x)| = f(x) Example: f(x) = x2 + 2x + 1 is O(x2) for C = 4 and k =1

4 Big-O Notation Show that f(x) = x2 + 2x + 1 is O(x2). When x > 1 we know that x x2 and 1 x2 then 0 x2 + 2x + 1 x2 + 2x2 + x2 = 4x2 so, let C = 4 and k = 1 as witnesses, i.e., f(x) = x2 + 2x + 1 < 4x2 when x > 1 Could try x > 2. Then we have 2x x2 & 1 x2 then 0 x2 + 2x + 1 x2 + x2 + x2 = 3x2 so, C = 3 and k = 2 are also witnesses to f(x) being O(x2). Note that f(x) is also O(x3), etc. 5

Big-O Notation Show that f(x) = 7x2 is O(x3). When x > 7 we know that 7x2 < x3 (multiply x > 7 by x2) so, let C = 1 and k = 7 as witnesses. Could try x > 1. Then we have 7x2 < 7x3 so, C = 7 and k = 1 are also witnesses to f(x) being O(x3). Note that f(x) is also O(x4), etc. 6 Big-O Notation Show that f(n) = n2 is not O(n). Show that no pair of C and k exists such that n2 Cn whenever n > k.

When n > 0, divide both sides of n2 Cn by n to get n C. No matter what C and k are, n C will not hold for all n with n > k. 7 Big-O Notation Observe that g(x) = x2 is O(x2 + 2x + 1) Def:Two functions f(x) and g(x) have the same order iff g(x) is O(f(x)) and f(x) is O(g(x)) 8

Big-O Notation Also, the function f(x) = 3x2 + 2x + 3 is O(x3) What about O(x4) ? In fact, the function Cg(x) is an upper bound for f(x), but not necessarily the tightest bound. When Big-O notation is used, g(x) is chosen to be as small as possible. 9 Big-Oh - Theorem Theorem: If f(x) = anxn+ an-1xn-1++ a1x+ a0 where ai R, i=0,n; then f(x) is O(xn). Leading term dominates!

Proof: if x > 1 we have |f(x)| = |anxn+ an-1xn-1++ a1x+ a0| |an|xn+ |an-1|xn-1++ |a1|x+ |a0| = xn(|an| + |an-1|/x ++ |a1|/xn-1 + |a0|/xn) xn(|an| + |an-1| ++ |a1| + |a0|) So,|f(x)| Cxn where C = |an| + |an-1| ++ |a1| + |a0| whenever x > 1 (whats k? k = 1, why?) Whats this: |a + b| |a| + |b| 10 Big-O Example: Prove that f(n) = n! is O(nn) Proof (easy): n! = 1 2 3 4 5 n nnnnnn = nn

where our witnesses are C = 1 and k = 1 Example: Prove that log(n!) is O(nlogn) Using the above, take the log of both sides: log(n!) log(nn) which is equal to n log(n) 11 Big-O Lemma:A constant function is O(1). Proof: Left to the viewer The most common functions used to estimate the time complexity of an algorithm. (in increasing O() order):

1, (log n), n, (n log n), n2, n3, 2n, n! 12 Big-O Properties Transitivity:if f is O(g) and g is O(h) then f is O(h) Sum Rule: If f is O(g ) and f is O(g ) then f +f is O(max(|g |,| 1 1 2 2 1 2 1

g2|)) If f1 is O(g) and f2 is O(g) then f1+f2 is O(g) Product Rule If f is O(g ) andf is O(g ) then f f is O(g g ) 1 1 2 2 1 2 1 2 For all c > 0,

O(cf), O(f + c),O(f c) are O(f) 13 Big-O Properties Example Example: Give a big-O estimate for 3n log (n!) + (n2+3)log n, n>0 1) For 3n log (n!) we know log(n!) is O(nlogn) and 3n is O(n) so we know 3n log(n!) is O(n2logn) 2) For (n2+3)log n we have (n2+3) < 2n2 when n > 2 so its O(n2); and (n2+3)log n is O(n2log n) 3) Finally we have an estimate for 3n log (n!) + (n2+3)log n

that is: O(n2log n) 14 Big-O Notation Def.:Functions f and g are incomparable, if f(x) is not O(g) and g is not O(f). f: R+R, f(x) = 5 x1.5 g: R+R, g(x) = |x2 sin x| 2500 2000 1500

-- 5 x1.5 -- |x2 sin x| 1000 -- x2 500 0 0 5

10 15 20 25 30 35 40 45

50 15 Big-Omega Notation Def.: Let f, g be functions with domain R0 or N and codomain R. f(x) is (g(x)) if there are positive constants C and k such that x > k, C |g (x )| |f (x )| C |g(x)| is a lower bound for |f(x)| |f(x)| C|g(x)|

k 16 Big-Omega Property Theorem: f(x) is (g(x)) iff g(x) is O(f(x)). Is this trivial or what? 17 Big-Omega Property Example: prove that f(x) = 3x2 + 2x + 3 is (g(x)) where g(x) = x2

Proof: first note that 3x2 + 2x + 3 3x2 for all x 0. Thats the same as saying that g(x) = x2 is O(3x2 + 2x + 3) 18 Big-Theta Notation Def.:Let f , g be functions with domain R0 or N and codomain R. f(x) is (g(x)) if f(x) is O(g(x)) and f(x) is (g(x)). C2|g(x)| |f(x)| C1|g(x)|

19 Big-Theta Notation When f(x) is (g(x)), we know that g(x) is (f(x)) . Also, f(x) is (g(x)) iff f(x) is O(g(x)) and g(x) is O(f(x)). Typical g functions: xn, cx, log x, etc. 20 Big-Theta Notation To prove that f(x) is order g(x)

Method 1 Prove that f is O(g(x)) Prove that f is (g(x)) Method 2

Prove that f is O(g(x)) Prove that g is O(f(x)) 21 Big-Theta Example show that 3x2 + 8x log x is (x2) (or order x2) 0 8x log x 8x2 so 3x2 + 8x log x 11x2 for x > 1. So, 3x2 + 8x log x is O(x2) (can I get a witness?) Is x2 O(3x2 + 8x log x)? You betcha! Why?

Therefore, 3x2 + 8x log x is (x2) 22 Big Summary Upper Bound Use Big-Oh Lower Bound Use Big-Omega Upper and Lower (or Order of Growth) Use Big-Theta 23

Time to Shift Gears Again Number Theory Number Theory Livin Large 24

Recently Viewed Presentations

  • 5th Grade Open Court Reading (2002) - henry anker

    5th Grade Open Court Reading (2002) - henry anker

    Our lockers are down the hall from the principal's office. 5th Grade Open Court Reading (2002) Word Knowledge Juggling Unit 1, Lesson 3 everyone everyone volleyball everyone volleyball homework everyone volleyball homework afternoon everyone volleyball homework afternoon then everyone volleyball...
  • APPALACHIAN REGIONAL COMMISSION Alabama Workshop August 28, 2019

    APPALACHIAN REGIONAL COMMISSION Alabama Workshop August 28, 2019

    The workshop will provide support to Appalachian communities in Alabama so that they may plan for effective use of ARC funding, understand Alabama's and ARC's investment priorities, discuss expectations for the applications, and help develop impactful projects.
  • Friendship Who are my best friends? What is

    Friendship Who are my best friends? What is

    * 'Two people are better off than one, for they can help each other succeed. If one person falls, the other can reach out and help. But someone who falls alone is in real trouble.' (New Living Translation) Ecclesiastes 4:9-10...
  • HALLOWE&#x27;EN

    HALLOWE'EN

    Halloween PowerPoint templates, free Halloween PowerPoint templates, free, PPT templates, PowerPoint tempaltes, tempaltes, slideshow templates Description Made by Leawo Software.
  • Defination and Brief History of Philiosophy of Realism

    Defination and Brief History of Philiosophy of Realism

    From Wikepedia.com. Contemporary philosophical realism is the belief in a reality that is completely ontologically independent of our conceptual schemes, linguistic practices, beliefs, etc. Philosophers who profess realism also typically believe that truth consists in a belief's correspondence to reality.
  • Πολυμεσικό Υλικό στο Internet: Συγχρονισμός, Επεξεργασία και ...

    Πολυμεσικό Υλικό στο Internet: Συγχρονισμός, Επεξεργασία και ...

    Example: Real Time Streaming Protocol (RTSP) For user to control display: rewind, fast forward, pause, resume, etc… Out-of-band protocol (uses two connections, one for control messages (Port 554) and one for media stream) RFC 2326 permits use of either TCP...
  • 28 - West Ada School District / Homepage

    28 - West Ada School District / Homepage

    Remove old sill and replace with new, pressure-treated sill. Reinforcing studs is best done by sistering. Hidden Structural Details. Study building and type of construction used. ... Headers are supported by resting them on trimmer studs.
  • Teachers&#x27; Conceptions of Mathematics and Intelligent Tutoring ...

    Teachers' Conceptions of Mathematics and Intelligent Tutoring ...

    Learning continuum used to develop LMALI questions in a three category progression: Exposure. Factual Literacy. Applicable Proficiency. Research Purpose. Develop a Agricultural Literacy Instrument for grades K-5 that aligns with the National Agricultural Literacy Outcomes (NALOs).