New User Special Price Expires in

Let's log you in.

Sign in with Facebook


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


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Discrete Math for CS

by: Ashleigh Dare

Discrete Math for CS ECS 020

Ashleigh Dare
GPA 3.75


Almost Ready


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

Purchase these notes here, or revisit this page.

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

Preview These Notes for FREE

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

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Engineering Computer Science

This 4 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 020 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 33 views. For similar materials see /class/191701/ecs-020-university-of-california-davis in Engineering Computer Science at University of California - Davis.

Similar to ECS 020 at UCD

Popular in Engineering Computer Science


Reviews for Discrete Math for CS


Report this Material


What is Karma?


Karma is the currency of StudySoup.

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

Date Created: 09/08/15
Lecture 11 572009 Announcements Ps6 out Due Tuesday Midterm back Tues May 12 Common functions see 34 in book mostly review I assume log exponent oor ceiling mod Skip 35 36 Recursively De ned Functions A recursive function is defined by referring to itself We saw this in defining Tn the minimum number of moves to shift n disks in the Tower of Hanoi problem Tn 1 n1 Tn 2 Tn l 1 for ngtl Domain codomain range N N a subset of N 2quotn l nl 2 Two key properties that make this type of definition work nonrecursive definitions for small base values and each time we refer to the function on the right side the argument is smaller than on the left side Book does n f0 1 fn n fnl n gt0 I ll do fibinacci function Def 32 in book FOF1 1 Fn Fn l Fn 2 for n gt1 F2 F2 1F22 Fl FO 1 1 2 F3 F31 F32 F2 F1 21 or expand F2 Give tree and better way to compute Function Fib0n If n0 OR nl Returnl39 Else ReturnFib0n l Fib0n2 Fibo is a recursive function Comments should make sure n not negative and declare n to be an integer Give tree of recursive calls Argue number of calls at least 2An2 Altemative A an array of size n AO e 139 Al e139 Fori 6 2tonDO Ai e Ai2 Ail39 Statement labeled is executed n2 times and we assume takes at most some constant about of time c time to look up or assign to an array so total time is at most 2c nl c n c c Note that the above is a function of n call it Tn known as a linear function if n is twice as large then time Tn is twice as much Function Growth rates 39 we skipped 37 and 38 will return to them later We want to be able to compare functions and want to ignore less important terms and constants Lets us compare how different programs perform for example in the example for Fibonacci the second program with Tn n c will significantly outperform the recursive one with 2An calls even if c is very large eventually and typically for moderate n Notation Big O and later 9 Big Theta and 9 big Omega We say x3 E 02 X Kind of like saying x3 le 2 X quotfor large x and if you don t care about constantsquot Def Def 34 from Schaum s Og f R gt R such that exists Ngt0Cgt0 st fn lt C gn for all ngtN You can actually forget about the and just imagine that f is nonnegative valued replace f by in case it s not Example nX lOOn E OnX YES 10 n2 E On2 YES lOn2 lOOn log N in On2 YES n log n in On2 YES n2 log in On log n NO As a practical matter it is pretty easy to get the right big 0 class for a function I throw away all constants multiplying terms or added to them eg le5 becomes X Note that you can t throw away constants that are exponents eg n2 can t throw away the 2 2 among terms added together throw away all but the fastest growing term apply to examples above How to prove things like this Suppose want to show 10 n logn 50n l E On log n must find a large enough C N such that 10 nlogn 50nl lt C nlog n for all n gt N What C N would you like would you like How about 10 nlogn 50n1 lt 61 nlog n Check true if 50n1 lt 51 nlogn Now 50n lt 50n log n if nge 3 So the above is true if 1 lt nlog n But for n gt 3 this is certainly true Doing it in the forward direction 1ltnlogn 10nlogn50n1lt10nlogn50nlognnlogn lt61nlogn when ngt3 n vs 2An n E O2An NO 2An E On Yes n nen sqrt21t n 1 O1n 1n n approx n 1n n n n lgn n nlgn n 2 nquot3 2An 10 4 10 40 100 10A3 1024 100 7 100 700 1000 10A6 10A30 1000 10 1000 10A4 10A6 10A9 10A300 g f R gt R eXists cCN such that 0 gm lt fn lt C gm Intuitively Ofn is all functions of growth rate fn or less fn is all functions of the same growth rate as fn


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

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

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

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


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


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:

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

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.