×

Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Tony Davis

6

0

17

Discrete Structures ENGR 213

Tony Davis
Christopher Newport University
GPA 3.82

Dali Wang

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Dali Wang
TYPE
Class Notes
PAGES
17
WORDS
KARMA
25 ?

Popular in Engineering and Tech

This 17 page Class Notes was uploaded by Tony Davis on Monday October 5, 2015. The Class Notes belongs to ENGR 213 at Christopher Newport University taught by Dali Wang in Fall. Since its upload, it has received 6 views. For similar materials see /class/219482/engr-213-christopher-newport-university in Engineering and Tech at Christopher Newport University.

×

Reviews for Discrete Structures

×

×

What is Karma?

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/05/15
Functions Complexity of Alorithms Section 22 The Growth of Functions Topics BigO Definition BigO by littleO Complexity Classes Properties and theorems of BigO Big Omega and Big Theta The Growth of Functions Overview What really matters in comparing the complexity of algorithms We only care about the behavior for large problems Even bad algorithms can be used to solve small problems Ignore implementation details such as loop counter increment etc We need to measure the order of complexity We quantify the concept that g grows at least as fast as f The Growth of Functions Overview Example algorithm Performance Estimating Running Time for Input of Size n If running then doubling input size For example time does following to run time grows like n doubles 1 hr gt 2 hrs n2 multiplies by 4 1 hr gt 4 hrs log2 n increase by small constant 1 hr 1 hr 1 min T2hne m F f squares it 1 hr gt60 hrss The BigO Notation Purpose to describe the growth rate of a func on eg does it grow like log n like n like n2 Examples 2n2 3n 1 grows like n2 05n log n 3n 7 grows like n log n BigO is used to denote an upper bound on growth rate fn grows no faster than gn The Growth of Functions The BigO De nition Formal definition fn is O9n if there is a constant C gt O and a constant k such that for all n gt k fn s Cgn In a better format Definition Let f and g be functions from N to R Then fis order 9 denoted f is 09 or 39f is bigO of g iff EIkEICVnn gt k gtfn S C gn Note Choose k Choose C it may depend on your choice of k Practically the function g is chosen to be as small as possible The Growth of Functions 5 BigO by De nition Example 1 fn n 3 O ltn3 nn2n for n gt 3 Therefore 17 3 is On Example 2 fn 4n2 n 0 54112 115412 n2 5112 for n gt 1 Therefore 4112 n is Onz The Growth of Functions BigO by De nition Example 3 Show that n3 is not 0100n2 If n3 is O1OOn2 then there are constants C and k such that n3 lt1OOCn2 for n gt k Then 17 lt1OOC for all n gt k This is a contradiction since n grows without bound The Growth of Functions BigO by LittleO Definition if limM o W gm then f is og called littleo of 9 Theorem Iff is og then fis Og It is usually easier to prove f is og using the theory of limits using L39Hospital39s rule An alternative for those with a calculus background The Growth of Functions Examples Example 1 3n 5 is Onz Proof It39s easy to show lim 3 j 5 0 Hencngogn 1 5 is on2 and so it is On2 Q E D Example 2 7n2 is Onz Example 3 7n2 is On3 Example 43 is On The Growth of Functions Complexity Classes Note that Og is a set called a complexity class It contains all the functions which 9 dominates Important Complexity Classes 01 g 0logng 0n g 0nlogn g0n2 g 004 g 06 g 0n where jgt2 and cgt1 The Growth of Functions Properties of BigO Theorem fxanx an1xquot1a1xaO is Ox Part 1 the set Og is closed under addition Iff is 09 and h is Og then f h is Og Example f1X2X2 0X2 f2xx22x1 Ox2 f3XX5 0X2 f1 X f2 X f3X3 The Growth of Functions Properties of BigO Part 2 the set Og is closed under multiplication by a scalar a real number lff is Og then at is Og Example f12x2 Ox2 f26x2 O g1x Ox gz100Xr O The Growth of Functions 12 BigO Theorems Theorem If f1 is C91 and f2 is Ogz then i f1f2 is Og1gz ii f1 f2 is Omax g1 92 Examples 1 f12n2 f23n f1f2 O f1f2 O 2 f15log n f25 1c1112 f1f2 The Growth of Functions BigO Theorems Proof of i There is a k1 and C1 such that 1 f1n lt C1g1n when n gt k1 There is a k2 and 02 such that 2 f2n lt ngzn when n gt k2 We must find a k3 and C3 such that 3 f1nf2n lt C3g1ngzn when n gt k3 We use the inequality if0ltaltband0ltcltdthenacltbd to conclude that f1nf2n lt C1czg1n92n as long as k gt maxk1 k2 so that both inequalities 1 and 2 hold at the same time Therefore choose C3 C102 and k3 maxk1 k2 Q E D The Growth of Functions 14 BigO Estimate Examples Example 1 Find BigO complexity class of the function fn3n2 15n Example 2 Find BigO complexity class of the function fn3n215nn13 Example 3 Find the complexity class of the function nn 3n2 3n100nn n2n If a op takes a nanosecond how long it takes to solve a problem for n50 The Growth of Functions 15 Big Omega and Big Theta Big 0 Big Omega and Big Theta Upper bound BigO Lower bound BigOmega Both upper and lower bound BigTheta The BigOmega Definition Let f and g be functions from N to R Then f is BigOmega of g denoted 29 iff EIkEICVnn gt k gtfn 2 Cl gn l The BigTheta Definition Let f and g be functions from N to R Then f is BigTheta of g denoted g iff is 09 and f is Qg The Growth of Functions 16

×

25 Karma

×

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over \$500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

Refund Policy

STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com