Algorithm analysis is a critical factor of computational complexity theory. It aids in evaluating the time and resources an algorithm requires to crack a given problem. Analysis of algorithms is the judgment of the quantity of time and space resources needed to execute it.
Table of Contents
- What is an Algorithm?
- Phases of Algorithm
- Complexity of Algorithm
- Characteristics of Algorithms
- What is Pseudocode
- Practice Problems
What is an Algorithm?
A set of rules or well-defined instructions that defines a series of operations to be carried out to decode a specific issue is known as an Algorithm.
In simple words, we can say that an algorithm is a procedure that accepts input as a collection of values and, in return, provides output by solving the problem.
Explore more about algorithms to get a better understanding of this topic.
Phases of Algorithm
The algorithm can be examined in 2 phases. The two analyses of an algorithm are as follows:
- Priori Analysis: Priori analysis is the theoretical analysis of an algorithm performed prior to its implementation. Before running or executing the algorithm, other parameters might be considered, such as the speed of the processor, which has no impact on the execution phase.
- Posterior Analysis: It is also known as the practical analysis of an algorithm. The algorithm is implemented in any computer language to obtain practical analysis. This analysis is used to determine how much running time and space the technique consumes.
Complexity of Algorithm
The performance of the algorithm can be estimated in two aspects:
- Time complexity: The amount of time required to accomplish the implementation is known as the time complexity of an algorithm. The time complexity of an algorithm is represented by the big O notation. Note: The big O is an asymptotic notation to represent the time complexity.
- Space complexity: The amount of space an algorithm needs while solving the problem is known as space complexity. It is also represented in big O notation.
Characteristics of Algorithms
- When it comes to algorithms, each instruction should be well-structured and defined.
- An algorithm should be input specified.
- An algorithm should be output specified.
- An algorithm should hold a number of steps, and it should get terminated after execution.
- An algorithm should be feasible to create each instruction.
- It should be flexible to bring out expected changes.
- An algorithm should take less time and memory space. In short, it should be efficient enough.
- An algorithm should be language independent.
What is Pseudocode?
It is nothing but a casual description of the functional principle of a program or an algorithm.
Practice Problems
Q1. There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays. The worst-case time
complexity of computing the median of the medians of A1, A2, …, An is ______.
(A) O(n)
(B) O(nlogn)
(C) O(n2)
(D) Ω(n2logn)
Q2. Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0]. The subsequence sum S(i,j)=∑jk=iA[k]. Determine the maximum of S(i,j), where 0≤i≤j<14. (Divide and conquer approach may be used).
Q3.Consider the following function from positive integers to real numbers:
10,n√,n,log2n,100n.
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is ________.
(A) log2n,100n,10,n√,n
(B) 100n,10,log2n,n√,n
(C) 10,100n,n√,log2n,n
(D) 100n,log2n,10,n√,n
Q4. An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ________.
Q5. Consider the following table:
| Algorithms | Design Paradigms |
| (P) Kruskal | (i) Divide and conquer |
| (Q) Quicksort | (ii) Greedy |
| (R) Floyd-Warshall | (iii) Dynamic Programming |
Match the algorithms to the design paradigms they are based on.
(A) (P)↔(ii),(Q)↔(iii),(R)↔(i)
(B) (P)↔(iii),(Q)↔(i),(R)↔(ii)
(C) (P)↔(ii),(Q)↔(i),(R)↔(iii)
(D) (P)↔(i),(Q)↔(ii),(R)↔(iii)
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
Comments