# Algorithms: Question Set – 14

#### How can we compare between two algorithms written for the same problem?

- The complexity of an algorithm is a method that is used to classify how effective it is in relation to other algorithms. [Case in point:] [Case in point:] [Case in point:] [C It focuses on how the quantity of the data collection that has to be processed can affect the amount of time it takes to complete the task. In computing, one of the most important aspects of an algorithm is its computational complexity. It is a good idea to classify algorithms according to the amount of time or space they require, and it is also a good idea to define the amount of time or space an algorithm requires as a function of the size of the input.
- The Complicated Nature of Time: The amount of time it takes to run a programme as a function of the magnitude of the data it receives is referred to as the program’s temporal complexity.
- The Complicated Nature of Space: The study of space complexity evaluates algorithms based on the amount of storage space they need to complete their tasks. Space complexity analysis was an extremely important field in the early days of computers (when storage space on the computer was limited).
- A word to the wise: Because there is so much storage available on computers these days, running out of room is hardly ever an issue. As a result, Time Complexity is the aspect of an Algorithm that is given the most weight while the algorithm is being evaluated.

#### What is the space complexity of the selection sort algorithm?

Because selection sort is an in-place sorting method, it does not need any additional or minimal data storage. This is because selection sort is an in-place sorting method. As a result, the space requirements of the selection sort algorithm are always the same, giving it an O(1) space complexity.

#### What do you understand by the best case, worst case and average case scenario of an algorithm?

- Asymptotic analysis is the method that establishes the mathematical framework upon which the performance of an algorithm is based during its execution. By utilising asymptotic analysis, we are able to quickly determine the best case, the average case, and the worst-case situations of an algorithm.
- The data arrangement in which an algorithm function most effectively is the best-case scenario for that algorithm. The best-case scenario for an algorithm is defined as the phrase “best-case scenario.” Consider, for instance, a binary search, in which the ideal circumstance would be for the target value to lie somewhere in the exact middle of the data that we are trying to find. In an ideal world, the time required to do a binary search would have a complexity of O(1), which is also known as constant time complexity.
- Worst-Case Scenario of an Algorithm The phrase “worst-case scenario of an algorithm” refers to the situation in which an algorithm is presented with the most problematic collection of input possible. For instance, the performance of quicksort could suffer if the pivot value was set to the item in a sublist that was either the largest or the smallest. The Quicksort algorithm will eventually degenerate into one that has a time complexity of O(n
^{2}), where n is the length of the list that needs to be sorted. - According to computational complexity theory, the “average case scenario” of an algorithm refers to the amount of some computational resource (typically time) that is used by the process, and it is calculated by averaging the amount of that resource required by the algorithm over all of the possible inputs. For instance, the complexity of the randomised quicksort algorithm in the average situation is O(n*log(n)), where n refers to the size of the list that needs to be sorted.

#### What is the space complexity of the insertion sort algorithm?

It is an in-place sorting approach, which means that it does not require any additional or minimal data storage. Insertion sort is one of the sorting methods. When doing an insertion sort, it is only necessary to keep a single list element in a location that is separate from the starting data. This results in a space complexity that is either constant or O(1).

#### What are few of the most widely used cryptographic algorithms?

A few of the most widely used cryptographic algorithms are as follows:

- IDEA
- CAST
- CMEA
- 3-way
- Blowfish
- GOST
- LOKI DES
- Triple DES.

#### Describe the heap sort algorithm.

- An algorithm for sorting that relies on comparisons is called heap sort.
- Heapsort is quite similar to selection sort in the sense that it first divides the data it receives into a sorted region and an unsorted region, and then gradually reduces the size of the unsorted region by removing the largest element from the unsorted part and adding it to the sorted region.
- The heapsort algorithm, in contrast to the selection sort algorithm, does not waste time scanning the unsorted region in linear time. Instead, the heapsort algorithm stores the unsorted region in a heap data structure, which enables it to more quickly determine which element is the largest at each step. Consider the following steps in the heap sort algorithm:
- The initial step of the Heapsort algorithm is to transform the list into a max heap.
- The algorithm then changes the first and last values in the list, which brings the total number of values that are taken into consideration by the heap operation down by one, and it filters the new first value into its place in the heap. This method is done numerous times until the range of values being considered contains just a single value.
- Use the buildMaxHeap() function when working with the list. Using O(n) operations, this function, which is also known as heapify(), can generate a heap from a list.
- Swap the positions of the items at the beginning and end of the list. Reduce by one the range of options that are being considered by the list.
- Use the shiftDown() method on the list to shift the new initial member to its correct index in the heap. This can be accomplished by using the function.
- Proceed to step 2 only if the list’s considered range contains more than one item.
- Note that the buildMaxHeap() operation only executes once and has a linear or O(n) time complexity depending on the size of the heap. The temporal complexity of the siftDown() function is O(log n), and it is called an infinite number of times. As a result, the time complexity of the heap sort algorithm is denoted by the notation O(n + n log (n)), which equals O. (n log n).

#### Define tree traversal and list some of the algorithms to traverse a binary tree.

The process of visiting all the nodes of a tree is known as tree traversal. Some of the algorithms to traverse a binary tree are as follows:

- Pre-order Traversal.
- In order Traversal.
- Post order Traversal.
- Breadth First Search
- ZigZag Traversal.

#### What do you understand by the Asymptotic Notations?

- The asymptotic analysis method is a methodology that is used for measuring the efficiency of an algorithm. This method does not rely on machine-specific constants, and it also prevents the algorithm from comparing itself to the more time-consuming approach. In the context of asymptotic analysis, the term “asymptotic notation” refers to a mathematical technique that can be utilised to represent the level of temporal complexity that an algorithm possesses.
- The three asymptotic notations that are most frequently used are listed below.
**Big Theta Notation:**- The theta Notation is used to precisely define the asymptotic behaviour of the function. It does this by binding functions from both the top and the bottom to determine behaviour. Theta notation can be easily obtained for an expression by omitting low-order terms and ignoring leading constants, which is a convenient way.

**Big Oh Notation:**- The Big O notation is a notation that defines an upper bound for an algorithm by bounding a function from above. Consider the issue of insertion sort: in the best-case scenario, it takes linear time, and in the worst-case scenario, it takes quadratic time. The complexity of time required for the insertion sort is O(n
^{2}). When we only have a maximum limit on the time complexity of an algorithm, it is useful to have this information.

- The Big O notation is a notation that defines an upper bound for an algorithm by bounding a function from above. Consider the issue of insertion sort: in the best-case scenario, it takes linear time, and in the worst-case scenario, it takes quadratic time. The complexity of time required for the insertion sort is O(n

**Big Omega Notation:**- The Notation provides an asymptotic lower bound on a function, similar to how the Big O notation does it. When we have a lower bound on the temporal complexity of an algorithm, it is helpful to utilise this technique.