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
