An algorithm refers to the sequential steps and processes that should be followed to solve a problem. There can be various kinds of algorithms devised to solve different problems although in programming we consider the following most important type of Algorithms to solve a problem.
What is an Algorithm?
An algorithm consists of instructions or steps that are followed in a specific order to solve a problem. Algorithms are used in many fields, including computer science, mathematics, and logistics. An algorithm is made of well-defined steps, including mathematical operations, conditional statements, and loops executed in a specific order.
1. Brute Force Algorithm
The simplest possible algorithm that can be devised to solve a problem is called the brute force algorithm. To device an optimal solution first we need to get a solution at least and then try to optimize it. Every problem can be solved by brute force approach although generally not with appreciable space and time complexity.
Later we will see this time complexity to be reduced to O (logn).
2. Recursive Algorithm
This is one of the simplest to devise algorithms as it does not require specifically think about every subproblem. This means we just need to think about the existing cases and the solution of the simplest subproblem, all other complexity will be handled by it automatically. Recursion is a very powerful tool although we should always take care of memory management here as recursion works using recursive stack which is called every time recursion function is invoked. Recursion simply means calling itself to solve its subproblems.
Time Complexity: O(n)
Although always remember to give the base case else the loop will continue to infinity giving memory error. This algorithm is simpler to design and implement.
a) Divide and Conquer Algorithm:
This is one of the most used algorithms in programming. This algorithm divides the problems into subproblems and then solve each of them and then combine them to form the solution of the given problems.
Again, it is not possible to solve all problems using it. As the name suggests it has two parts: Divide the problem into subproblems and solve them.
- Combine the solution of each above problems.
- This algorithm is extensively used in various problems as it is quite stable and optimal for most of the problems asked.
b) Dynamic Programming Algorithms:
This is the most sought out algorithm as it provides the most efficient way of solving a problem. Its simply means remembering the past and apply it to future corresponding results and hence this algorithm is quite efficient in terms of time complexity.
Dynamic Programming has two properties:
- Optimal Substructure: An optimal solution to a problem contains an optimal solution to its subproblems.
- Overlapping subproblems: A recursive solution contains a small number of distinct subproblems.
This algorithm has two version:
- Bottom-Up Approach: Starts solving from the bottom of the problems i.e. solving the last possible subproblems first and using the result of those solving the above subproblems.
- Top-Down Approach: Starts solving the problems from the very beginning to arrive at the required subproblem and solve it using previously solved subproblems.
c) Greedy Algorithm:
In this algorithm, a decision is made that is good at that point without considering the future. This means that some local best is chosen and considers it as the global optimal. There are two properties in this algorithm.
- Greedily choosing the best option
- Optimal substructure property: If an optimal solution can be found by retrieving the optimal solution to its subproblems.
Greedy Algorithm does not always work but when it does, it works like a charm! This algorithm is easy to device and most of the time the simplest one. But making locally best decisions does not always work as it sounds. So, it is replaced by a reliable solution called Dynamic Programming approach.
d) Backtracking Algorithm:
It is an improvement to the brute force approach. Here we start with one possible option out of many available and try to solve the problem if we are able to solve the problem with the selected move then we will print the solution else we will backtrack and select some other and try to solve it. It is a form of recursion, it’s just that when a given option cannot give a solution, we backtrack to the previous option which can give a solution, and proceed with other options.
3. Randomized Algorithm
This is an algorithm type that makes its decision on the basis of random numbers i.e. it uses random numbers in its logic.
The best example of this is choosing the pivot element in quicksort. This randomness is to reduce time complexity or space complexity although not used regularly. Probability plays the most significant role in this algorithm.
In terms of quicksort, we fail to choose the correct element we might end up with a running time of O(n^2 ) in the worst case. Although if chosen with proper interpretation it can give the best running time of O(nlogn).
- Randomized Quick Sort
- Kager’s Algorithm etc.
4. Sorting Algorithm:
This type of Algorithm is used to rearrange the list of elements so that they are in a specific order. the default order of sorts is ascending order.
There are various types of sorting algorithms but the common ones are bubble sort, insertion sort, heap sort and merge sort.
In terms of bubble sort, if the array is required to be sorted in reverse order then O(n^2 ) could be the worst case. Although if the array is already sorted then the time complexity is O(n). The average time complexity is O(n^2 ) when array elements are in jumble order.
5. Searching Algorithm:
This type of Algorithm is used to search for an item in the data structure like in an array.
There are basically two types of searching i.e. linear search and binary search. The linear search checks for each element in the data structure until the value is found while in binary search the search space is get reduced to half at each step, so it is faster than linear search.
In terms of time complexity, the linear O(n) and the binary search will take O(long)
6. Hashing Algorithm:
A hashing algorithm is a function that maps data of arbitrary size to a fixed-size value and the value is known as a hash or a hash code.
Hashing algorithms are used in a variety of applications, such as cryptography, data structures, and databases.
Benefits of using Hashing:
- It provides a fast lookup in data structure
- Reduced storage space
- It is used in verifying data integrity
To know more about the courses, click here.
Frequently Asked Questions
Can algorithms be used to solve every problem?
Algorithms can be used to solve most of the problems but it does not guarantee to solve every problem as some problems are too complex to be solved. For example, the halting problem is a problem that cannot be solved by any algorithm.
Which algorithm is more efficient and why?
There is no such algorithm which is best in every scenario it depends on the problem it is trying to solve. Hence. the best algorithm for a given problem depends on the specific characteristics of the problem.
Which algorithm is used for prediction?
There are many algorithms that can be used for prediction. some common prediction algorithms like Linear regression, Logistic regression, Decision trees and Neural networks. Choosing the right algorithm depends on the specific characteristics of the data and the required accuracy of the predictions.
Are algorithms always accurate?
No algorithms are always accurate, it depends on the quality of the data it is trained on and the complexity of the problem it is trying to solve. Even the best algorithms could generate false results.
What are the 5 characteristics of an algorithm?
The five main characteristics of an algorithm are well-defined input and output, unambiguity, finiteness, language independence, and effectiveness and feasibility. Any algorithm that is meant to work effectively is bound to have these characteristics.
This article briefly discussed the most important type of algorithms. We discussed the theoretical aspect, applications and step-by-step approach of various important algorithms. We hope this blog has helped you learn about the most important type of algorithms. If you like to learn more, you can check out our articles:
- Greedy Algorithms
- Julia Programming Language
- Introduction to C Programming
- Data Structure
- Introduction to Machine Learning
- Types of information system
Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming and many more! If you wish to test your competency in coding, check out the mock test series and take part in the contests hosted on Coding Ninjas Studio!