CHAPTER 4
Searching & Algorithm Analysis
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original content from your professor.
By Prof. Rafael Orta, M.S.
https://quizizz.com/
Last week we covered
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.
Agenda for this week
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.
Linear (Serial) Search
Linear search steps through part of an array one item at a time looking for a desired item. The search stops when the item is found or when the search has examined each item without success.
The technique is often used because it is easy to write and is applicable to many situations.
See whiteboard example
Linear Search (Pseudocode)
Using linear search and if given a list of 10,000 elements, and if each comparison takes 2 µs, what is the longest possible runtime for linear search?
Linear search works perfectly is you are searching a small array, However, if a search is done over a large array it is worthwhile to find a faster algorithm. Imagine if the only way to get to your contacts in your phone was by scrolling one by one until you get to the phone of your friend Zuckerberg Mark. ☺
A/ The longest possible runtime happens if the element you are looking for is at the end of the list or is not in the list, thus 20,000 µs is the longest.
Given a list of 10,000 elements, and if each comparison takes 2 µs, what is the fastest possible runtime for linear search?
A/ The fastest possible runtime happens if the element you are looking for is at the beginning of the list, thus 2 µs is the fastest.
Let’s examine the Linear Search program in C++
Selection Sort
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty, and the unsorted part is the entire list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right. This algorithm is not suitable for large data sets as its average and worst-case complexities are of Ο(n2), where n is the number of items.
Selection Sort (Pseudocode)
Let’s examine the selection sort program in C++
Binary Search
Binary Search
1.- What is the first contact searched?
2.- What is the second contact searched?
Given a list of 1024 elements, what is the runtime for binary search if the search key is less than all elements in the list?
Let’s check the Binary Search program
Constant time operations
When the time required by a function does not depend on the size of the input, the procedure is called a constant time which is written O(1).
“in practice, designing an efficient algorithm aims to lower the amount of time that an algorithm runs. However, a single algorithm can always execute more quickly on a faster processor. Therefore, the theoretical analysis of an algorithm describes runtime in terms of number of constant time operations, not nanoseconds. A constant time operation is an operation that, for a given processor, always operates in the same amount of time, regardless of input values. “
True or False, a loop is never a constant time operation.
Growth of functions and complexity
Upper and lower bounds
An algorithm with runtime complexity T(N) has a lower bound and an upper bound.
Growth of functions and complexity
Growth rates and asymptotic notations
An additional simplification can factor out the constant from a bounding function, leaving a function that categorizes the algorithm's growth rate. Ex: Instead of saying that an algorithm's runtime function has an upper bound of 30N2, the algorithm could be described as having a worst-case growth rate of N2. Asymptotic notation is the classification of runtime complexity that uses functions that indicate only the growth rate of a bounding function. Three asymptotic notations are commonly used in complexity analysis:
O notation provides a growth rate for an algorithm's upper bound.
Ω notation provides a growth rate for an algorithm's lower bound.
Θ notation provides a growth rate that is both an upper and lower bound (average).
Suplemental Informational Video (To watch at home)
Growth of functions and complexity
Big O Notation
“Big O notation is a mathematical way of describing how a function (running time of an algorithm) generally behaves in relation to the input size. In Big O notation, all functions that have the same growth rate (as determined by the highest order term of the function) are characterized using the same Big O notation. In essence, all functions that have the same growth rate are considered equivalent in Big O notation.
Given a function that describes the running time of an algorithm, the Big O notation for that function can be determined using the following rules:
Big O Notation
Which of the following Big O notations is equivalent to O(N+9999)?
A: O(1) B: O(N) C: O(9999)
Big O Notation
Runtime growth rate
One consideration in evaluating algorithms is that the efficiency of the algorithm is most critical for large input sizes. Small inputs are likely to result in fast running times because N is small, so efficiency is less of a concern. The table below shows the runtime to perform f(N) instructions for different functions f and different values of N. For large N, the difference in computation time varies greatly with the rate of growth of the function f. The data assumes that a single instruction takes 1 μs to execute.
Algorithm Analysis
Worst-case algorithm analysis
“To analyze how runtime of an algorithm scales as the input size increases, we first determine how many operations the algorithm executes for a specific input size, N. Then, the big-O notation for that function is determined. Algorithm runtime analysis often focuses on the worst-case runtime complexity. The worst-case runtime of an algorithm is the runtime complexity for an input that results in the longest execution. Other runtime analyses include best-case runtime and average-case runtime. Determining the average-case runtime requires knowledge of the statistical properties of the expected data inputs. “
Algorithm Analysis
Counting constant time operations
“For algorithm analysis, the definition of a single operation does not need to be precise. An operation can be any statement (or constant number of statements) that has a constant runtime complexity, O(1). Since constants are omitted in big-O notation, any constant number of constant time operations is O(1). So, precisely counting the number of constant time operations in a finite sequence is not needed.”
Ex: An algorithm with a single loop that execute 5 operations before the loop, 3 operations each loop iteration, and 6 operations after the loop would have a runtime of f(N) = 5 + 3N + 6, which can be written as O(1) + O(N) + O(1) = O(N). If the number of operations before the loop was 100, the big-O notation for those operation is still O(1).
Recursive Definitions
Recursion is an elegant method of solving many computer problems that relies on the capability of a function to continue calling itself until it satisfies a particular condition.
Recursive algorithm is an algorithm that breaks the problem into smaller subproblems and applies the algorithm itself to solve the smaller subproblems.
Recursive function is a function that calls itself. Recursive functions are commonly used to implement recursive algorithms.
Video
Analyzing the time complexity of recursive algorithms
Recurrence relations
“Using O-notation to express runtime complexity of a recursive function requires solving the recurrence relation. For simpler recursive functions such as binary search, runtime complexity can be determined by expressing the number of function calls as a function of N.”