### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 1.RunningTime.pdf CS 5343

UTD

GPA 3.5

### View Full Document

## 205

## 0

## Popular in Data Structure & Algorithm Analysys

## Popular in ComputerScienence

This 5 page Class Notes was uploaded by Yue YU on Monday October 5, 2015. The Class Notes belongs to CS 5343 at University of Texas at Dallas taught by Dr. Neeraj K Gupta in Fall 2015. Since its upload, it has received 205 views. For similar materials see Data Structure & Algorithm Analysys in ComputerScienence at University of Texas at Dallas.

## Reviews for 1.RunningTime.pdf

### 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: 10/05/15

The Function of Algorithm is to do something with input data and then get the output according to our requirement Examplel when you see the traffic signals at the intersection Red means stop and green means you can go In this case the color ofthe signal is input our reaction is output and the rules are algorithm Example2 find max element of an array Algorithm arrayMaxA n Input array A of n integers Output maximum element ofA currentMax lt A O forilt 1ton 1do if AU gt currentMax then currentMax lt A i return currentMax The type of output in computer can be integer float string and so on Running Time The running time of an algorithm typically grows with the input size Sometimes the running time is different with the same size and same algorithm Characterizes running time as a function of the input size n Seven functions that often appear in algorithm analysis I Constant z 1 l Logarithmic z log n l Linear z n l N Log N z n log n l Quadratic z n2 l Cubic z n3 l Exponential z 2 By inspecting the pseudocode we can determine the maximum number of primitive operations executed by an algorithm as a function of the input size Algorithm arrayMaxA n currentMax lt A O forilt 1ton 1do if AU gt currentMax then currentMax lt A i operations 2n 2n 1 2n 1 increment counter i 2n 1 return currentMax 1 Total 8n 2 CI Algorithm arrayMax executes 8n 2 primitive operations in the worst case Define a Time taken by the fastest primitive operation b Time taken by the slowest primitive operation CI Let Tn be worst case time of arrayMax Then a 8n 2 S Tn S b8n 2 CI Hence the running time Tn is bounded by two linear functions BigOh Notation CI Given functionsfn and gn we say thatfn is 0gn if there are positive constants c and no such that fn S cgn for n 2 no CI Example 2n 10 is 0n l 2n 10 S an I c 2 n 2 10 l n 2 10c 2 l Pickc 3 and no 10 CI 3n3 20n2 Sis 0n3 CI need c gt O and no 2 1 such that 3n3 20n2 5 S cm3 for n 2 no CI this is true for c 28 and no 1 BigOh Rules CI If is fn a polynomial of degree d then fn is 0nquot ie I Drop lowerorder terms I Drop constant factors CI Use the smallest possible class of functions I Say quot2n is 0n instead of quotZn is 0n2 CI Use the simplest expression of the class I Say quot3n 5 is 0n instead of quot3n 5 is 03n CI Example I We determine that algorithm arrayMax executes at most 8n 2 primitive operations I We say that algorithm arrayMax quotruns in 0n time Prefix Averages Quadratic it The following algorithm computes prefix averages in quadratic time by applying the definition it Algorithm prefixAveragesl X n 33 Input array X of n integers Output array A of prefix averages of Xoperations A lt new array of n integers n forilt Oton 1do n s lt XO n forjlt 1toido 12n 1 lt9 lt9 lt9 lt9 lt9 slt sXi 12n 1 lt9 Ailt si1 n lt9 returnA 1 lt9 The running time of prefixAveragesl is 01 2 n lt9 The sum of the first n integers is nn 1 2 lt9 Thus algorithm prefixAveragesl runs in 0n2 time

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

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

#### "I made $350 in just two days after posting my first study guide."

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

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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