1.RunningTime.pdf CS 5343
Popular in Data Structure & Algorithm Analysys
Popular in ComputerScienence
verified elite notetaker
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
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
Are you sure you want to buy this material for
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'