Algorithms and Asymptotic Notations

• Algorithms are well-defined procedures or sets of rules that allow computers to solve problems.

Standard Notations

• Standard notations in algorithms are mathematical representations and symbols that are commonly used to describe and analyze algorithms.

Asymptotic Notations

• Asymptotic notations are a way to describe the efficiency of algorithms using rate of growth.
• These notations characterize the running time or space usage of an algorithm as the input size grows.
• Big O notation represents the upper bound of an algorithm's running time, indicating the worst-case scenario.
• Small o notation signifies a non-inclusive upper bound, meaning the algorithm's running time is strictly less than the specified function.
• Omega notation denotes the lower bound of an algorithm's running time, indicating the best-case scenario.
• Theta notation defines a tight bound, meaning the algorithm's running time is both upper-bounded and lower-bounded by the specified function.

Analysis of Sorting Algorithms

• Worst-case analysis evaluates the maximum amount of time or resources an algorithm might require.
• Best-case analysis determines the minimum amount of time or resources an algorithm could use.
• Average-case analysis assesses the expected performance of an algorithm over a range of inputs.
• Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure and has a time complexity of O(n log n).
• Shell sort is an in-place sorting algorithm that improves upon insertion sort by allowing exchanges of elements that are far apart and has a time complexity of O(n log n) in the average case.
• Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value and has a time complexity of O(nk), where n is the number of elements and k is the number of digits.
• Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time and has a time complexity of O(n^2) in the worst and average cases.
• Selection sort is an in-place comparison sorting algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list and has a time complexity of O(n^2).
• Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them in the wrong order and has a time complexity of O(n^2).

Analysis of Searching Algorithms

• Sequential search, also known as linear search, checks each element of a list in order until the desired value is found or the entire list has been searched.
• Binary search is an efficient algorithm for finding an item from a sorted list of items.
• Fibonacci search is a search algorithm that uses Fibonacci numbers to find the required element in a sorted array.
• Recursive algorithms involve calling themselves within their own definition and are used to solve problems that can be broken down into smaller, self-similar subproblems
• Analyzing recursive algorithms involves determining their time complexity, often through recurrence relations.
• Analyzing control structures involves assessing how loops, conditional statements, and other control flow mechanisms affect an algorithm's overall performance.