### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Data Structures CSCI 3230

GSU

GPA 3.52

### View Full Document

## 60

## 0

## Popular in Course

## Popular in ComputerScienence

This 45 page Class Notes was uploaded by Leonor Kulas on Monday October 12, 2015. The Class Notes belongs to CSCI 3230 at Georgia Southern University taught by Debopam Acharya in Fall. Since its upload, it has received 60 views. For similar materials see /class/221982/csci-3230-georgia-southern-university in ComputerScienence at Georgia Southern University.

## Similar to CSCI 3230 at GSU

## Reviews for Data Structures

### 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/12/15

Time and Space Complexities ALGORITHM ANALYSIS I Measures the ef ciency of an algorithm or its implementation as a program as the input size becomes very large I We evaluate a new algorithm by comparing its performance with that of preVious approaches 1 Comparisons are asymptotic analyses of classes of algorithms I We usually analyze the time required for an algorithm and the space required for a data structure M2 Lecture Notes Time and Space Complexities 39 M ALGORITHM ANALYSIS I Many criteria affect the running time of an algorithm including i39 speed of CPU bus and peripheral hardware design think time programming time and debugging time language used and coding efficiency of the programmer i39 quality of input good bad or average I Programs derived from two algorithms for solving the same problem should both be 1 Machine independent 1 Language independent 3 Environment independent load on the system 1 Amenable to mathematical study 1 Realistic M2 Lecture Notes Time and Space Complexities 3 ALGORITHM ANALYSIS In lieu of some standard benchmark conditions under which two programs can be run we estimate the algorithm39s performance based on the number of key and basic operations it requires to process an input of a given size For a given input size n we eXpress the time T to run the algorithm as a function Tn If size of input is important we need a method for comparing the two programs over the allowable input sizes while looking only at the most important part of the timing function the two may cross over somewhere l Approach compare asymptotic growth rates of functions we investigate what happens in the limit when the size of input approaches in nity M2 Lecture Notes Time and Space Complexities 4 39 i ALGORITHM ANALYSIS I Thus we can provide simpler functions that approximate asymptotically a given function This is important since a time function may not have a closed form or if it has one it may be too complex for us to understand I We determine the goodness of an approximation by comparing the growth rates of the original function and that function39s approximations l Concept of growth rate allows us to compare running time of two algorithms without writing two programs and running them on the same computer M2 Lecture Notes Time and Space Complexities 5 39 Big oh Notation O I The O symbol was introduced in 1927 to indicate relative growth of two functions based on asymptotic behavior of the functions I De nition Let T and f be two functions Then T 0f if there is a natural number 110 and a positive real constant c which may depend on the chosen no such that for all natural numbers n larger than 110 Tn cfn l eg ifTnlOOOn and fnn2 n0 Z 1000 and c 1 then TnO f lfn0 and we say that Tn 0fn M2 Lecture Notes Time and Space Complexities Big oh Notation O I Examples E 3n2On as 3n2lt4n for all ngt2 E 10 n2 4n 2 0n2 as 10 n2 4n 2 lt 11 n2 for all ngt5 El 3n2 01 as 3n2 is not less than or equal to c for any constant c and all ngtn0 M2 Lecture Notes Time and Space Complexities 39 I Big oh Notation O I The statement Tn 0fn states that fn is an upper bound on the value of Tn for all n ngtn0 It does not say anything about how good this bound is I For the statement Tn 0fn to be informative fn should be as small a function of n as one can come up with for which Tn 0fn So we often say that 3n3 On we almost never say that 3n3On2 even though this statement is correct I Constants can be ignored Units are not important 07n2 0n2 I Lower order terms are ignored Compare relative growth only On37n23 0n3 M2 Lecture Notes Time and Space Complexities 8 CLASSIFICATION OF FUNCTIONS Logarithmic function I A function Tn is said to be of at most logarithmic growth if Tn 0log n I Common in programs which solve a big problem by transforming it into a smaller problem by cutting size by some constant fraction some sorts eg I Whenever 11 doubles log 11 increases by a constant but log 11 doesn39t double until 11 increases to n2 M2 Lecture Notes Time and Space Complexities 9 Linear function I A function Tn is said to be of at most linear growth if Tn 0n I Small amount of processing is done on each input element As value of n grows running time grows in the same proportion Doubling n roughly doubles the running time I Optimal situation for algorithms that must process 11 inputs or produce 11 outputs eg n assignments in a forloop going 1 to 11 M2 Lecture Notes Time and Space Complexities 10 Quadratic Function I A function Tn is said to be of at most quadratic growth if Tn 0n2 I Occurs when algorithm processes all pairs of data items eg nested loop When 11 doubles running time increases fourfold I When nlOOO running time is 1 million M2 Lecture Notes Time and Space Complexities 1 1 Polynomial function I A function Tn is said to be of at most polynomial growth if Tn 0nk for some natural number k 3 1 I If k 3 algorithm with this running time processes triples of data items Practical only for small problems M2 Lecture Notes Time and Space Complexities 12 Exponential function I A function Tn is said to be of at most exponential growth if there is a constant c such that Tn 0c and c gt 1 l Few exponential algorithms are appropriate Fibonacci series is example I Sometimes used as brute force solution to problems When n 20 running time is 1 million M2 Lecture Notes Time and Space Complexities 13 Factorial function I A function Tn is said to be of at most factorial growth if Tn 0n M2 Lecture Notes Time and Space Complexities 14 Constant function I A function Tn is said to have constant running time if the size of the input 11 has no effect on the running time of the algorithm eg assignment of a value to a variable I The equation for this algorithm is Tn c M2 Lecture Notes Time and Space Complexities 15 5n log n M2 Lecture Notes Time and Space Complexities 50 16 Input size n M2 Lecture Notes Time and Space Complexities 17 2 Omega Notation I Tn Qfn if there is a natural number nO and a positive real constant c which may depend on the chosen no such that for all natural numbers n 3 no Tn cfn I In general terms Tn Qfn means fn is a lower bound on Tn M2 Lecture Notes Time and Space Complexities 18 2 Omega Notation 7n23n5 0n4 7n23n5 0113 7n23n5 0112 7n23n5 2112 7n23n5 Qn 7n23n5 01 n2 and 7n2 3n Sgrows at the same rate 7n23n5 0n2 Qn2 9n2 M2 Lecture Notes Time and Space Complexities 19 0 theta Notation Tn Gfn if and only if TnOfn and TN Qfn I In general terms Tn Gfn means growth rate of Tn equals growth rate of fn M2 Lecture Notes Time and Space Complexities 20 0 little 0 notation I Tn ofn if Tn Ofn and Tn not equal Thetafn ii Little 0 implies that T39s growth rate is strictly less than that off I eg Tn log n and fn n2 M2 Lecture Notes Time and Space Complexities 21 Review of the notations I Big O and Big Theta represent the asymptotic behavior of functions by using the 5 and relationships I 3 and lt relationships are represented by Omega and little 0 M2 Lecture Notes Time and Space Complexities 22 THEOREMS I If T1 Of T2 09 where all functions are from N to the positive reals then i a T1 T2 maxOfOg E bT1T2 Ofg I If Tx is a polynomial of degree n then Tx 6x M2 Lecture Notes Time and Space Complexities 23 THEOREMS I If fn is in Ogn and gn is in Ohn then fn is in Ohn I If fn is in Okgn for any constant kgt0 then fn is in Ogn M2 Lecture Notes Time and Space Complexities 24 39 Using Big 0 Notation I Ogn denotes the set of all functions fn such that fn 5 c gn for some constant cgt0 Thus quotfn is Ognquot means that fn is a member of the set of functions Ogn I IVith2this meaning we can write such statements as n2 O n is n I That is for all cgt0 there is a constant dgt0 such that n2 Ch 5 dn2 for all n 3 0 M2 Lecture Notes Time and Space Complexities 25 Examples I 2n3 3n2 n 2n3 3n2 0n 2n3 O n2 n 2n3 O n2 0n3 0n4 M2 Lecture Notes Time and Space Complexities Examples I 2n3 3n2 n 2n3 3n2 0n 2n3 G n2 n 2n3 6 n2 6n3 M2 Lecture Notes Time and Space Complexities THINGS TO REMEMBER IN ANALYSIS Constants or loworder terms are ignored l eg if fn 2n2 then fn 0n2 Most important resource to analyze is running time other factors are algorithm used and input to the algorithm Parameter N usually referring to number of data items processed affects running time most significantly l N may be degree of polynomial size of file to be sorted or searched number of nodes in a graph etc M2 Lecture Notes Time and Space Complexities 28 39 I Running time Calculations I When we analyze an algorithm or a program fragment we consider the key and basic operation involved in the execution of the algorithm for a large problem size I For a sorting algorithm this is usually the number of comparisons I For loops involving sums we count the number of mathematical operations that are performed M2 Lecture Notes Time and Space Complexities 29 Example 1 I Assuming sum is an integer initialized to 0 find the complexity TFn for the following program fragment TFn is the count of the number of integer operations for the variable sum in the fragment do not count the array accesses or the assignment operations Number of Operations are shown against the lines I for int i0 ilt n1 i do 2 from i Oto n sum sum i Ai 2 for int j0 j lt i j do 2 from j O to i sum sum j Anj 2 endforj forintk1kltnkdo HZ from k1ton sum sum i Ak Ai 3 endfork endfori M2 Lecture Notes Time and Space Complexities 30 Example 1 I Step1 Represent the code with summation using 2 notations n i n 39TFn 2 2 2 22 3 i0 j0 k1 l Step2 Simplify and solve the summation to know more about summations refer to the end of this PowerPoint M2 Lecture Notes Time and Space Complexities 31 Example 1 I Step 2 To solve for TFn we simplify the series as follows n TFn z 2 2i1 3n i0 n Z 4 2i 3n i0 n 4n1 22 i 3nn1 i0 4n 4 2n n12 3n2 3n 4n2 8n 4 M2 Lecture Notes Time and Space Complexities 32 39 Example 2 I lfthe code fragment contains a function call then the time of the call must be added in as well I For example Say the complexity of the subroutine Tmysubm n3 when input is size n for all cases ie best average and worstcase are all the same n3 What is the complexity of the following fragment where TFn is the count ofthe number of additions to the variable sum in the fragment for int i0 ilt n1 i do for intjO j lt i j do sum sum j mysubj endforj endfori M2 Lecture Notes Time and Space Complexities 33 Example 2 I This loop is translated into the following summation n i TFltngtZ Zlt2j3gt iOjO M2 Lecture Notes Time and Space Complexities 34 Analyzing by inspection I We can also use inspection and informal counting to determine the run time of an algorithm Here are some general rules I Consecutive statements Maximum statement is the one counted eg a fragment with single forloop followed by double forloop is On2 M2 Lecture Notes Time and Space Complexities 35 Analyzing by inspection I IfElse For fragment if cond then 81 else 82 running time is never more than the running time of the test plus the larger of the running times of 81 and 82 M2 Lecture Notes Time and Space Complexities 36 39 I Analyzing by inspection I For Loops I Running time of a forloop is at most the running time of the statements inside the forloop times number of iterations for i sum O i lt n i sum ai I In this loop there are n1 comparisons and n increments initializing costs 1 unit I the loop requires 2 time units on each iteration assignment and addition I total time is Tn 2n 2 n n1 4n 3 M2 Lecture Notes Time and Space Complexities 37 Analyzing by inspection I Nested ForLoops for i 0 i lt n i for j 0 sum aO j lt i j sum ai initialize i 1 time 1 increment i n times n initializej and sum 2n compare i n times for each i in On1 we incrementj assign jth value to sum 2i for i1 to n1 M2 Lecture Notes Time and Space Complexities 38 Analyzing by inspection 13n2i13n212n1 n1 i or explicitly Z Z 2 i0 jO M2 Lecture Notes Time and Space Complexities 39 Strategy for analysis I analyze from inside out I analyze function calls first M2 Lecture Notes Time and Space Complexities 40 Common Functions I Exponential functions a Cl 61171 26117111 m n mn Cl Cl Cl M2 Lecture Notes Time and Space Complexities 41 Common Functions I Logarithms I x logba is the exponent for a bx I Natural log In a logea I Binary log 1g a log2a I lgza 1g a2 I lglga 1glga logcab log a log 9 10gb a nlogba 1 10gb a Ogc a log 9 logb1a logb a lo a 2 gb log 9 loc loa agb Cgb M2 Lecture Notes Time and Space Complexities 42 39 Common Functions I If the base of a logarithm is changed from one constant to another the value is altered by a constant factor J lEX log10 n log210 log2 n l Base of logarithm is not an issue in asymptotic notation lgn n lg n D Prove using Stirling s approximation in the text for lgn M2 Lecture Notes Time and Space Complexities 43 39 Common Functions Summations Why do we need summation formulas For computing the running times of iterative constructs loops MaXSubvcctorA n maxsum lt 0 for z39 lt 1 to 72 do for j z39 to n sum lt O for k lt z39 to j d0 sum Ak maxsum lt maXsum maxsum return maxsum onmi jl i1 ji ki M2 Lecture Notes Time and Space Complexities 44 Summations I Constant Series For integers a and b a S b i1b a1 I Linear Series Arithmetic Series For n 2 0 Zi12nnn 1 i1 2 I Quadratic Series For n 2 0 fi21222unzzw 6 1 1 M2 Lecture Notes Time and Space Complexities 45

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

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