# CMPT 225 Lecture 6 Review of Complexity Analysis

CMPT 225 Lecture 6 Review of Complexity Analysis using the Big O notation + Comparing List ADT class implementations 1 Last Lecture We saw how to Create linked list Perform operations on a linked list Create a Node class Implement a List ADT class: Using an array

Using a linked-list 2 Learning Outcomes At the end of this lecture, a student will be able to: Complexity Analysis: Analyze the best, worst, and average case running time of various ADT operations implemented by various data structures Abstract Data Types (ADTs): Given a set of requirements, select the most appropriate

data collection ADT class, taking into account its time and space efficiency 3 Todays menu Review of the Big-O notation Compare the various implementations of our List ADT class: Position-oriented versus value-oriented Array-based implementation versus link-based implementation 4

Satisfying Clients Requirements When developing a solution, we must, as part of our design (Step 2) Choose the data collection ADT (List, Stack, Queue, etc) that would best solve the problem along with its most efficient implementation In order to make these choices We compare time efficiency and/or space efficiency of various implementations (i.e., data structure + algorithms) of the chosen ADT

5 Time/Space Efficiency Time efficiency of an algorithm is a measure of time the algorithm requires to execute Space efficiency of an algorithm is a measure of space (e.g. memory, secondary storage) the algorithm requires to execute Expressed using Big O notation 6 Big O Notation

Introduced by P. Bachmann & Edmund Landau Upper bound approximation n -> size of data This approximation is good enough, since we are interested in the time and space efficiency of algorithms as n -> (i.e. as the size of data collection manipulated by algorithms increases to infinity) 7 When the efficiency of an algorithm is found to be

O(g(n)), we say that its efficiency is of order g(n) g(n) -> complexity categories Commonly used Complexity Categories 8 g(n): 1, log n, n, n log n, n2, nk, kn When an algorithm has a time/space efficiency of O(1) > we say that its time/space efficiency is constant O(log n -> logarithmic

O(n) -> linear O(n2) -> quadratic O(nk) -> polynomial O(kn) -> exponential Comparing O(g(n)) as size of data collection n -> n ->

9 Source: http://jsdo.it/Boony/big-o-notation How to find the efficiency of an algorithm and express it using the Big O notation? Consider an algorithm is its execution time (or its space) a function of n? If YES, then select this function of n, i.e., g(n) that expresses its efficiency:

O(log n), O(n), O(n log n), O(n2), O(nk) or O(kn) If NO, i.e., its execution time (or its space) is not a function of n, hence it is independent of n, then as n -> , it is constant, so its efficiency is O(1) 10 Big O Notation - Arithmetic Sequential statements O(s1 + s2) = max[ O(s1), O(s2) ] Repeated statements O(k * n) = O(n) if k is constant

Nested statements O(s1 * s2) = O(s1) * O(s2) 11 Activity - Time Efficiency Analysis Problem Statement: Determine whether array B is a scrambled version of array A. Both arrays have length n. Test case 1 Input: A[1,1,3,3,5] and B[3,5,1,1,1] Expected result: B is not a scrambled version of

A Test case 2: Input: A[6,7,8, 9] and B[9,8,7,6] Expected result: B is a scrambled version of A 12 We can develop 2 algorithms to solve the above problem statement and analyze their time efficiency to determine which of the 2 algorithms is the most time efficient Activity - Time Efficiency Analysis Algorithm 1

13 Activity - Time Efficiency Analysis Algorithm 2 14 Activity Best/Average/Worst case scenarios Which element(s) (i.e., test case data) shall I be looking for in this sequence

5 7 2 1 8 9 11 3 4 15 6 in order to obtain the best case scenario of linear searchs time efficiency? worst case scenario of linear searchs time efficiency? 15 Back to :Array-based implementation List ADT Public interface List Class attributes

(private): FriendsBook (client code) Etc... Remove array of Profile objects Search 16

Link-based implementation List ADT Public interface Inser t FriendsBook (client code) Class attributes (private):

Remove linked list of Profile objects Search 17 List Comparing both implementations of the position-oriented List ADT using Big O notation Time efficiency of their operations (worst case

scenario): Operations getElementCount insert remove removeAll 18 retrieve array-based link-based

Comparing both implementations of the value-oriented List ADT using Big O notation Time efficiency of their operations (worst case scenario): Operations getElementCount insert remove removeAll 19 retrieve (search)

array-based link-based Learning Check We can now Determine the time/space efficiency of an algorithm using the Big O notation Compare the various implementations of our List ADT class: Position-oriented versus value-oriented Array-based implementation versus link-based

implementation 20 Next Lecture Another linear data collection -> Stack 21

## Recently Viewed Presentations

• Kennings . Beowulf. Composed by single Christian author for a Christian audience . Sometime in the 8th -11th centuries . Epic Poem . Comitatus - Germanic code of loyalty. Thanes - warriors swearing loyalty to kings in return for land,...
• Three rules are used to build the electron configuration: Aufbau principle Pauli Exclusion Principle Hund's Rule Aufbau Principle Electrons occupy orbitals of lower energy first. Pauli Exclusion Principle An orbital can hold only two electrons and they must have opposite...
• A stopwatch should advance each second. A forever loop will increase the time as long as the program is running. Stop and Reset. Stop and Reset. GET READY. GET READY. ADD THIS CODE. TRY IT. Control your stopwatch with the...
• chaosgroup.com. Global leader in computer graphics, over 20 years experience . V-Ray is the industry standard for top design studios, architectural firms, advertising agencies, and visual effects companies
• The construction line ellipse is then traced over with an object line. Sketching Isometric Circles. The process is repeated where the other end of the cylinder occurs. It should be noted that only part of the second ellipse will be...
• Joseph "Jojo" Giorgianni. \$900. ... was arrested for an incident stemming back to last July. Fayleallegedly diverted a check for \$17,364.63 from the Black River Watershed Project to cover a shortage in the town's Property Tax account. ... and this...
• Acri.Tec GmbH, Germany Acri.Sil-oI 1000, Acri.Sil-oI 5000 Micromed, Italy PDMS 1000, PDMS 2000, PDMS 5000 Alcon, USA Silicone™ 1000
• NDP TARGETS "The Department of Basic Education plan is to increase the number to 300 000 by 2024, with 350 000 learners passing mathematics and 320 000 learners passing physical science.The Commission proposes a target for 2030 of 450 000...