×

### Let's log you in.

or

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

×

or

by: Yue YU

205

0

5

# 1.RunningTime.pdf CS 5343

Yue YU
UTD
GPA 3.5
Data Structure & Algorithm Analysys
Dr. Neeraj K Gupta

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

How to describe the running time of an algorithm
COURSE
Data Structure & Algorithm Analysys
PROF.
Dr. Neeraj K Gupta
TYPE
Class Notes
PAGES
5
WORDS
KARMA
25 ?

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

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

×

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

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

Amaris Trozzo George Washington University

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

Steve Martinelli UC Los Angeles

Forbes

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

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