DSA - Ch02 - Measuring Efficiency with Big O.pdf

Measuring Efficiency with Big O 1 Measuring Efficiency with BigO Notation - Introduction ❖We want a quantifiable way to measure how efficient certain data structures are at different tasks ❖Efficiency is crucial for tasks such as searching, modifying, and accessi...

Measuring Efficiency with Big O 1 Measuring Efficiency with BigO Notation - Introduction ❖We want a quantifiable way to measure how efficient certain data structures are at different tasks ❖Efficiency is crucial for tasks such as searching, modifying, and accessing elements ❖BigO Notation is the industry standard for measuring the efficiency of algorithms and data structures ❖It helps in comparing different approaches and selecting the best one based on performance Searching Modifying Accessing 2 What is BigO Notation? ❖BigO Notation describes the O(2n) O(n2) performance or complexity of an algorithm. CPU operations / time O(n) ❖It provides an upper bound on the time (or space) required by an algorithm as a function of the input size (n) O(log n) O(1) Input size (n) 3 Criteria for BigO Notation ❖Scoring data structures based on: Accessing elements: How quickly can we retrieve an element? Searching for an element: How quickly can we find an element? Inserting an element: How quickly can we add an element? Deleting an element: How quickly can we remove an element? Accessing elements Searching for an element Inserting an element Deleting an element 4 Performance Report for BigO Notation ❖Using BigO Notation to create a performance report card for data structures. ❖Compare and contrast different structures based on their BigO scores. 5 Time Complexity Equations ❖A Time Complexity Equation works by inserting the size of the data-set as an integer n, and returning the number of operations that need to be conducted by the computer before the function can finish ❖These equations estimate the number of operations needed for an algorithm to complete N = The Size of the Data Set (Amount of elements contained within the Data Structure) 6 Time Complexity Equations N = 10 the number of operations that need to be conducted by the computer before completion of that function Accessing Searching Inserting Deleting Equation Equation Equation Equation We always use the worst-case scenario when judging these data structures 2 8 50 Operations Operations Operations 42 1898 Operations Operations 7 Meaning of BigO ❖It’s called BigO notation because the syntax for the Time Complexity equations includes a BigO and then a set of parentheses The parenthesis houses the function A Function Time Complexity Constant Time random() O of 1 O(1) 8 Measuring Efficiency with BigO? ❖We measure efficiency in # of operations performed because measuring by how long the function takes to run would be silly Measuring by time is biased towards better hardware > Speed = Operations 9 Measuring Efficiency with BigO Notation - Quick Recap We measure efficiency based on 4 metrics Accessing Searching Inserting Deleting Modeled by an equation which takes in size of data-set (n) and returns number of operations needed to be performed by the computer to complete that task What the data structure is good at, and what the data structure is bad at 10 Measuring Efficiency with BigO Notation - Quick Recap ❖The efficiency of a data structure isn't the only factor to consider when choosing which one to use in your program. ❖Some have specific quirks or features that set them apart. Accessing Searching Inserting Deleting BigO Notation - Types of Time Complexity Equations ❖Let’s dive straight into what the actual equations mean in terms of efficiency 6 most common Time Complexity Equations O(1) O(n) O(log n) O(n log n) O(n²) O(2n) 12 BigO Notation – O(1) ❖O(1): The absolute best data structure can “score” on each criteria is O(1) ❖No matter what the size of your data set is, the task will be completed in a single instruction When we graph Volume of Data vs # Of Instructions Required # Of Operations remains constant 14 BigO Notation – O(1) ❖O(1): known as constant time complexity ❖The time it takes to complete an operation or an algorithm does not depend on the size of the input. ❖The execution time remains constant regardless of how large the input is. ❖One of the simplest and most efficient time complexities. Operations Size of Dataset (N) 1 requires 10 1 requires 50 1 requires 1000 15 BigO Notation – O(1) ❖Characteristics of O(1) Algorithms Constant Execution Time: The algorithm or operation completes in the same amount of time, regardless of the size of the input. Direct Access: Often involves operations like accessing a specific element in an array, performing arithmetic operations, or retrieving a value from a hash table. Predictable Performance: The running time does not change with varying input sizes. O(1) Example 17 BigO Notation – O(n) ❖O(n): known as linear time complexity, ❖The time it takes to complete the algorithm grows linearly with the size of the input, denoted as n Operations Size of Dataset (N) 10 requires 10 50 requires 50 1000 requires 1000 18 BigO Notation – O(n) ❖Characteristics of O(n) Algorithms Proportional Growth: The running time increases proportionally with the input size. Single Pass: Often, the algorithm involves a single pass over the input data. Examples: Simple loops that iterate over all elements of an input. 19 O(n) Example 1 20 O(n) Example 2 What Time Complexity (BigO )is this? 21 O(n) Example ❖It is approximately double that of Example #1, both of them have a runtime of O(n). ❖Big-O analysis doesn't necessarily give a direct comparison of the performance of two functions ❖It focuses on the kind of growth a runtime incurs as a function's input grows. 22 BigO Notation – O(log n) ❖O(log n): known as logarithmic time complexity, ❖Describes an algorithm whose running time increases logarithmically as the size of the input increases. ❖This typically occurs in algorithms that divide the problem space in half at each step, such as binary search and certain tree operations. ❖Gets more efficient as the size of the data set increases Number of Operations Number of Operations Number of Operations Increases Way More Skyrockets Increases More Slowly Slowly 23 BigO Notation – O(log n) ❖Characteristics of O(log n) Algorithms Halving the Input: The algorithm reduces the problem size by a constant fraction (commonly by half) at each step. Efficient Scaling: As the input size grows, the number of additional steps required grows slowly. Typical Examples: Binary search, search trees. 24 O(log n) Example middle = (L+H) / 2 step1 M = 10+9 / 2 step2 M = (M+1 = 5+9)/2 = 7 step3 M = (L=5 + H=M-1=6) /2 = 5 25 O(log n) Example O(log n) Example – part I O(log n) Example – part II BigO Notation – O(n²) ❖O(n²), known as quadratic time complexity, ❖Describes an algorithm whose performance is directly proportional to the square of the size of the input data set. ❖This complexity typically arises in algorithms that involve nested iterations over the input data. 29 BigO Notation – O(n²) ❖Characteristics of O(n²) Algorithms Nested Loops: Most commonly, O(n²) time complexity results from a piece of code that contains nested loops, each of which iterates over the input. Rapid Growth: The execution time increases significantly as the input size increases. Common in Brute Force Algorithms: Algorithms that compare every pair of elements in a dataset often exhibit O(n²) complexity. 30 O(n²) Example ❖Bubble Sort is a classic example of an O(n²) algorithm. ❖It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. 4 3 1 2 5 compare & swap 31 O(n²) Example 4 3 1 2 5 compare & swap 32 BigO Notation – O(2n) ❖O(2n), known as exponential time complexity, ❖Describes an algorithm whose growth doubles with each addition to the input data set. ❖This type of complexity is typically seen in algorithms that solve problems by generating all possible combinations of the input data, often seen in brute-force solutions to combinatorial problems. 33 BigO Notation – O(2n) ❖Characteristics of O(2n) Algorithms Doubling Growth: The execution time doubles with each increment in the input size. Exponential Increase: Even small increases in input size lead to massive increases in the time required to run the algorithm. Combinatorial Explosion: Common in problems involving combinations and permutations where the number of possible states grows exponentially. Typical in Recursion: Often found in recursive algorithms that solve problems by exploring all possible choices or states. 34 O(2n) Example ❖Recursive Fibonacci Sequence 35 O(2n) Example ❖Recursive Fibonacci Sequence 36 Measuring Efficiency with BigO Notation - Final Note on Time Complexity Equations O(2n) O(n2) CPU operations / time O(n) O(log n) O(1) Input size (n) 37 Measuring Efficiency with BigO Notation - Summary By understanding these patterns and structures, you can better analyze and determine the time complexity of algorithms in your code ❖Constant Time (O(1)): Directly accessing elements or performing simple arithmetic operations. Example: ❖Linear Time (O(n)): Single loop iterating through all elements of an array or collection. Example: 38 Measuring Efficiency with BigO Notation - Summary By understanding these patterns and structures, you can better analyze and determine the time complexity of algorithms in your code ❖Logarithmic Time (O(log n)): Halving the problem space each time, such as in binary search. Example: 39 Measuring Efficiency with BigO Notation - Summary By understanding these patterns and structures, you can better analyze and determine the time complexity of algorithms in your code ❖Quadratic Time (O(n^2)): Nested loops where the inner loop runs for every iteration of the outer loop. Example: ❖Exponential Time (O(2^n)): Recursive calls where each call generates multiple new calls, typically seen in brute-force algorithms for combinatorial problems. Example: 40 Measuring Efficiency with BigO Notation - Final Note on Time Complexity Equations ❖Time Complexity Equations are NOT the only metric you should be using the gauge which data structure to use ❖Some provide other functionality that make them extremely useful Other Some Data Structure Functionality 41