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

Algorithm Design and Analysys - Week 4 Notes

by: Judy

Algorithm Design and Analysys - Week 4 Notes CSC 3110

Marketplace > Wayne State University > Computer Science and Engineering > CSC 3110 > Algorithm Design and Analysys Week 4 Notes
GPA 3.64

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

Chapter 2 material covered. Topics include Analysis Framework Measuring Input Size and Running Time Primitive Operations Order of Growth Worst, Best and Average Case Big O, Big Omega, Big T...
Algorithm Design and Analysis
Alaa Khalaf Al-Makhzoomy
Class Notes
algorithms, BigO, analysis, InputSize
25 ?




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.


Reviews for Algorithm Design and Analysys - Week 4 Notes


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/23/16
OneNote Online 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 efficiency with respect to running me and memory space Time Efficiency (me complexity): how fast an algorithm runs Space Efficiency (space complexity): amount of memory required in addion to input and output We will focus on me efficiency Measuring Input Size We look at efficiency 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 influenced 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 difficulty in clocking the actual running me of the program Could count the number of mes the algorithm's operaons are executed – both really difficult and unnecessary The thing to do – idenfy the most importan operaon of the algorithm (the basic operaon, usually the most me consuming operaon) Time efficiency 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 Efficiency 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 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)) iff 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 different orders of growth for different 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


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

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

Janice Dongeun University of Washington

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

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

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.