### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithm Design and Analysys - Week 4 Notes CSC 3110

WSU

GPA 3.64

### View Full Document

## About this Document

## 5

## 0

## Popular in Algorithm Design and Analysis

## Popular in Computer Science and Engineering

This 2 page Class Notes was uploaded by Judy on Friday September 23, 2016. The Class Notes belongs to CSC 3110 at Wayne State University taught by Alaa Khalaf Al-Makhzoomy in Fall 2016. Since its upload, it has received 5 views. For similar materials see Algorithm Design and Analysis in Computer Science and Engineering at Wayne State University.

## Similar to CSC 3110 at WSU

## Popular in Computer Science and Engineering

## Reviews for Algorithm Design and Analysys - Week 4 Notes

### 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/23/16

OneNote Online https://onenote.officeapps.live.com/o/onenoteframe.aspx?ui=en-US&rs=... Week 4 Notes Tuesday, September 20, 20161:00 PM *Note: This also includes material that was covered in the video lecture to make up for a missed day during week 3 CHAPTER 2 Review properes of logarithms and become familiar with them Also review properes of summaons and become familiar with them Lastly, review proof techniques The Analysis Framework Analysis of algorithms is looking at eﬃciency with respect to running me and memory space Time Eﬃciency (me complexity): how fast an algorithm runs Space Eﬃciency (space complexity): amount of memory required in addion to input and output We will focus on me eﬃciency Measuring Input Size We look at eﬃciency as a funcon of n indicang input size Somemes choice of a parameter indicang input size maers (matricies) Choice of the appropriate size metric can be inﬂuenced by the operaons of the algorithm Somemes the input is one number and the magnitude of the number determines the input size Units for Measuring Running Time There are drawbacks to using units of me (seconds/miliseconds etc) Dependent on the speed of the computer/machine Dependent on the quality of the program using the algorithm and of the compiler There is diﬃculty in clocking the actual running me of the program Could count the number of mes the algorithm's operaons are executed – both really diﬃcult and unnecessary The thing to do – idenfy the most importan operaon of the algorithm (the basic operaon, usually the most me consuming operaon) Time eﬃciency is analyzed by determining the number of repeons of the basic operaon as a funcon of input size (n) Should be used with cauon, as if does not account for operaons that are not basic, but it can give a reasonable esmate of the algorithm's running me Primive Operaons Basic computaons performed by an algorithm Assumed to take a constant amount of me Examples: evaluang an expression, assigning to a variable, indexing an array, calling a method, returning from a method. Orders of Growth For large values of n, the funcons order growth is what counts The funcon growing the slowest is the logarithmic funcon Exponenal 2^n and n! Grow extremely fast Worst Case Eﬃciency for the worst case input of size n for which the algorithm runs the longest among all possible inputs of that size Bounds the running me from above Guarantees that the running me will not exceed that amount Best Case Where the algorithm runs the fastest among all possible inputs of that size Bounds the running me from below Average Case Must make some assumpons about possible inputs of size n Divide all instances of n into several classes so that the number of mes the basic operang is executed is the same OneNote Online https://onenote.officeapps.live.com/o/onenoteframe.aspx?ui=en-US&rs=... Big O O(g(n)), all funcons with a lower or same order growth as g(n) Big Omega Omega(g(n)) - all funcons with a higher or same order of growth as g(n) Big Theta Theta(g(n)) - set of all funcons that have the same order of growth as g(n) Properes of Asymptoc orders of growth •f(n) € O(f(n)) •f(n) € O(g(n)) iﬀ g(n) € W(f(n)) •If f (n) € O(g (n)) and g(n) € O(h(n)), then f(n) € O(h(n)) •If 1 (n) € O1g (n)) an2 f (n) € 2(g (n)), then f (n) + f (n) € O(max{g (n), g (n)}) 1 2 1 2 Using Limits for comparing orders of growth Much more convenient method for comparing orders of growth Compute the limit of the ratio of the two functions in question If limit = zero, top has smaller order of growth than bottom If limit = c , top has the same order of growth as bottom If limit = ∞, top has a larger growth order than bottom Useful Asymptotic Observations All logarithmic functions log base a of n belong to the same class Theta(log n) for all a>1 All polynomials of the same degree k belong to the same class Exponential functions a^n have diﬀerent orders of growth for diﬀerent a's Order log n < order n^a (a>0) < order a^n < order n! < order n^n Simple Loops Time Complexity: T(n) = (a constant c) * n = cn = O(n) Nested Loops T(n) = cn^2 = O(n^2) Sequence T(n) = O(n) Logarithmic Time Algorithm Binary Search Exponential Time Algorithms Towers of Hanoi

### 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

#### "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."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "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."

#### "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."

### 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

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.