Most Important Type of Algorithms

2. 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.

For example:

#include <iostream>
using namespace std;

// Searching for an element in a sorted array of elements
int main() {
    int arr[] = {1, 2, 3, 4, 6}; // sorted array
    int search = 5; // search for 5
    bool flag = false;
    for (int i = 0; i < 5; i++) { // Time Complexity: O(n)
        if (arr[i] == search)
            flag = true;
    }
    if (flag == true)
        cout << "found";
    else
        cout << "not found";
    return 0;
}

Later we will see this time complexity to be reduced to O (logn).

3. 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.

For Example:

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.

4. 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).

Applications of Randomized Algorithm

• Randomized Quick Sort
   
• Kager’s Algorithm etc
   

For example 

5. 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.

For example

6. Search engine algorithm

A search engine algorithm is a complex system that analyzes and ranks web pages based on various factors, such as relevance, quality, and popularity. For example, when you search for "best Italian restaurants" on Google, the algorithm considers elements like the content, user engagement, and backlinks of different web pages to determine the most relevant and authoritative results to display to you.

7. 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) 

For example

8. 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.

Advantages of using Hashing Algorithm:

• It provides a fast lookup in data structure 
   
• Reduced storage space
   
• It is used in verifying data integrity
   

For example

9. Greedy Algorithm

A greedy algorithm makes the locally optimal choice at each stage, aiming for the global optimum. It builds up a solution incrementally without reconsidering previous decisions. For instance, in the "Coin Change" problem, a greedy algorithm would select the largest coin denomination at each step to minimize the number of coins used to reach the target sum.

10.Divide-And-Conquer Algorithm

A divide-and-conquer algorithm breaks down a complex problem into smaller, more manageable subproblems, solves them independently, and then combines the solutions to solve the original problem. For example, the Merge Sort algorithm divides an unsorted array into halves, recursively sorts each half, and then merges the sorted halves back together to obtain the final sorted array.

11. Backtracking Algorithm

A backtracking algorithm explores all possible solutions by incrementally building candidates to the solution and abandoning a candidate ("backtracking") as soon as it determines that the candidate cannot lead to a valid solution. For instance, in the "N-Queens" problem, the algorithm places queens on a chessboard one by one, checking for conflicts, and backtracks when a placement leads to an invalid solution.

12. Dynamic Programming Algorithm

Dynamic programming is an algorithmic technique that solves complex problems by breaking them down into overlapping subproblems and storing the results to avoid redundant calculations. It follows the principle of optimal substructure and subproblem overlap. For example, in the "Fibonacci Sequence" problem, dynamic programming stores previously calculated Fibonacci numbers to efficiently compute the next number in the sequence.

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.

What is the most common type of algorithm?

The most common type of algorithm is the sorting algorithm, with examples like QuickSort, MergeSort, and BubbleSort, widely used for arranging data in a specific order.

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.

Conclusion

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! 

Happy Learning!