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


by: Yue YU

1.RunningTime.pdf CS 5343

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

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

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

How to describe the running time of an algorithm
Data Structure & Algorithm Analysys
Dr. Neeraj K Gupta
Class Notes
25 ?




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.

Similar to CS 5343 at UTD

Popular in ComputerScienence


Reviews for 1.RunningTime.pdf


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


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

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

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

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.