×

### Let's log you in.

or

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

×

or

23

0

12

# Class Note for CS 357 at UA-Data Structures (8)

Marketplace > University of Alabama - Tuscaloosa > Class Note for CS 357 at UA Data Structures 8

No professor available

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.
No professor available
TYPE
Class Notes
PAGES
12
WORDS
KARMA
25 ?

## Popular in Department

This 12 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Alabama - Tuscaloosa taught by a professor in Fall. Since its upload, it has received 23 views.

×

## Reviews for Class Note for CS 357 at UA-Data Structures (8)

×

×

### 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: 02/06/15
CS 357 Data Structures Class 08 January 30 2002 Announcements Chapter 4 sections 1 and 2 for next time omework 2 due tonight by 1159 pm omework 3 due in class Monday February 4 ook for the courseware CD this week possibly tomorrow Bama and obviously bama mail is down because of server damage from the power problems yesterday Seebeck hopes to have it back by noon today Spring 2002 CS 357 Class Notes Page 2 How do we analyze algorithms Primitive Operations Count the number of low level operations performed at each step of the algorithm What is the best case vs worst case of arrayMax Problems Algorithm arrayMaxAn Input An array A storing ngt1 integers Output The maximum element in A currentMax A0 fori 6 1 to n1 do if currentMax lt Ai then currentMax 6 AU return currentMax Spring 2002 CS 357 Class Notes Page 3 BigOh Notation Takes the worstcase bigpicture approach fn is Ogn ifthere are positive constants c gt O and n021 such that fn S c gn for every n 2 n0 Examples 2n6 is On n2 is not On fn2n6 26 27 mumquot 2I 22 23 24 25 20 i 20 2l 22 2 24 2S 2 27 Spring 2002 cs 357 Class Notes page A BigOh Rules 1 2 P NFDP 8 If dn is Ofn then adn is Ofn for any constant a gt 0 If dn is Ofn and en is Ogn then dn en is Ofn 9n f dn is Ofn and en is Ogn then dnen is Ofngn f dn is Ofn and fn is Ogn then dn is Ogn f fn is a polynomial of degree d then fn is Ond nX is Oa for any fixed xgt0 and agt1 log nX is OIog n for any fixed xgt0 loan is OnY for any fixed constants xgt0 and ygt0 Spring 2002 CS 357 Class Notes Page 5 Example 2n3 4n2 log n By ru e 8 log n is On By ru e 3 4n2 log n is O4n3 By ru e 2 2n3 4n2 log n is O2n3 4n3 By ru e 1 or 5 2n3 4n3 is On3 By ru e 4 2n3 4n2 log n is On3 Spring 2002 CS 357 Class Notes Page 6 Simple Rules Drop lower order terms and constant factors 2n3 4n2 log n O2n3 4n2 log n On3 When evaluating code focus on iteration Could be by recursion Spring 2002 CS 357 Class Notes Page 7 BigOh Questions 2000 n 5 is O 45 n4 32 n3 12n 45 is O 2 log n 300 log log n is O 4300 is O is O 3n Spring 2002 CS 357 Class Notes Example Array Max Algorithm arrayMaxAn Input An array A storing ngt1 integers Output The maximum element in A currentMax AO fori 6 1 to n1 do if currentMax lt Ai then currentMax Ai return currentMax Spring 2002 CS 357 Class Notes Page E Example Selection Sort Algorithm selectionSort An Input An array storing n21 integers Output A sorted array in A for currentPos 6 O to n2 do currentMax AcurrentPos maxPos currentPos for findPos currentPos1 to n1 do if AfindPos gt currentMax then currentMax 6 AfindPos maxPos findPos if maxPos currentPos swap AmaxPos and AcurrentPos return A Spring 2002 CS 357 Class Notes Page 1 Terminology Getting progressively worse Constant is 01 Logarithmic is OIog n Linear is On Quadratic is On2 Polynomial is Onk where k 2 1 Exponential is Oa where a gt 1 Spring 2002 CS 357 Class Notes Page 1 Relatives of the BigOh Big Omega fn is Qgn if gn is Ofn Big Theta fn is gn if fn is Ogn and fn is Qgn LittleOh if for any constant c gt 0 there is a constant n0 gt 0 such that fn s c gn for n 2 no LittleOmega if for any constant c gt 0 there is a constant n0 gt 0 such that gn s c fn for n 2 no m zn6 L gi4u 23 24 2s 2 27 23 24 25 20 27 gnn 2O 239 22 20 2 22 20 21 22 23 24 25 26 27 20 21 22 23 24 25 26 27 111ng 2002 CS 357 Class Notes

×

×

### BOOM! Enjoy Your Free Notes!

×

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

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

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

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