Types of Algorithm and its Classification
Every Algorithm falls under a specific class. The Algorithms’ speed is measured in terms of many basic operations it performs. From increasing order of growth they are classified as follows:
a. Constant Time Algorithm
b. Logarithmic Algorithm
c. Linear Time Algorithm
d. Polynomial Time Algorithm
e. Exponential Time Algorithm
Formally, the complexity of algorithms is derived using the asymptotic notation. These are formal notational methods for stating the growth of resource needs (storage and efficiency) of an algorithm. There are four basic notations used when describing resource needs. These are: O(f(n)), o(f(n)), \Omega(f(n))Ω(f(n)), and \Theta(f(n))Θ(f(n)) – Big-O, Little-o, Omega and Theta respectively.
a. Big O: O(f(n)) establishes an upper bound on the function. This is used to denote the worst-case runtime of an Algorithm.
b. Omega: Θ(f(n)) It defines two functions that bound the function g(n) from both top and both top and bottom for appropriate values for constants c1, c2,n0. This function is used to denote the average runtime of an algorithm.
c. Theta: Ω(f(n)) It defines a lower bound of the function. We can use it to indicate the Best care runtime of an algorithm.
Types of Algorithm
There are many types of algorithms, but the most fundamental purpose of classification is to highlight the various ways in which a problem can be solved.
1. Simple Recursive Algorithm: It solves the base cases directly and then recurs with a simpler subproblem. It does some extra work to convert the solution to a simpler subproblem by breaking the problems into a more straightforward or a smaller problem of the same kind. For example;
a. To count the number of elements in a list:
– If the list is empty, return zero; otherwise,
– Step past the first element, and count the remaining elements in the list
– Add one to the result
b. To test if a value occurs in a list:
– If the list is empty, return false; otherwise,
– If the first thing in the list is the given value, return true; otherwise
– Step past the first element, and test whether the value occurs in the remainder of the list
2. Backtracking Algorithm: A backtracking Algorithm is based on a depth-first recursive search. It tests to see if a solution has been found, and if so, returns it; otherwise, for each choice which can be made at this point – Make a choice, Recur, and If the recursion returns a solution, return it. If no options then remain, return failure.
For example: To colour a map with no more than four colours:
a colour (Country n)
– If all countries have been coloured (n > number of countries) return success; otherwise,
– For each colour c of four colours,
i) If country n is not adjacent to a country that has been coloured c
· Color country n with colour c
· recursively colour country n + 1
· If successful, return success
b Return failure (if loop exits)
3. Dynamic Programming Algorithm: A dynamic programming algorithm remembers past results and uses them to find new results. Dynamic programming is generally used for optimisation problems in which, Multiple solutions exist, need to find the best one. It requires optimal substructure and overlapping subproblem. Optimal substructure – Optimal solution contains optimal solutions to subproblems. Overlapping subproblems – Solutions to subproblems can be stored and reused in a bottom-up fashion. This differs from Divide-and-Conquer, where subproblems generally need not overlap.
E.g., Fibonacci Numbers:
a. To find an nth Fibonacci number:
– If n is zero or one, return one; otherwise
– Compute, or look up in a table, Fibonacci (n-1) and Fibonacci (n-2)
– Find the sum of these two numbers
– Store the result in a table and return it
b. Since finding the nth Fibonacci number involves finding all smaller Fibonacci numbers, the second recursive call has little work to do.
c. The table may be preserved and used again.
4. Divide and Conquer: A divide and conquer algorithm consists of two parts.
a. Divide the problem into smaller subproblems of the same type and solve these subproblems recursively.
b. Combine the solutions to the subproblems into a solution to the original problem
Traditionally, an algorithm is only called divide and conquer if it contains two or more recursive calls. For example;
a. Quicksort: Partition the array into two parts, and quicksort each of the parts. No additional work is required to combine the two sorted parts.
b. Mergesort: Cut the array in half, and mergesort each half. Combine the two sorted arrays into a single sorted array by merging them.
5. Binary Tree Lookup: Here is how to look up something in a sorted binary tree:
a. Compare the key to the value in the root
– If the two values are equal, report success
– If the key is less, search the left subtree
– if the key is greater, search the right subtree
This is not a divide and conquer algorithm, although there are two recursive calls, only one is used at each level of recursion. For example:
a To find the nth Fibonacci number:
– If n is zero or one, return one; otherwise,
– Compute Fibonacci (n-1) and Fibonacci (n-2)
– Return the sum of these two numbers
b. This is an expensive algorithm
– It requires O(Fibanocci(n)) time
– This is equivalent to exponential time, that is, O(2n)
6. Brute force algorithm: It tries all possibilities until a satisfactory solution is found. Such an algorithm can be:
a. Optimising: Find the best solution. This may require finding all solutions, or if a value for the best solution is known, it may stop when any best solution is found
– Example: Finding the best path for a travelling salesman
b. Satisficing: Stop as soon as a solution is found that is good enough
– Example: Finding a travelling salesman path that is within 10% of optimal
However, improving the Brute force algorithm often requires exponential time. Various heuristics and optimisations can be used.
– Heuristic: A “rule of thumb” that helps you decide which possibilities to look at first
– Optimisation: In this case, a way to eliminate specific options without fully exploring them
7. Greedy Algorithm: An optimisation problem is one in which you want to find, not just a solution, but the best solution. A “greedy algorithm” sometimes works well for optimisation problems. A greedy algorithm works in phases: At each stage:
– You take the best you can get right now, without regard for future consequences
– You hope that by choosing a local optimum at each step, you will end up at a global optimum
Example of Count Money: Suppose you want to count out a certain amount of money, using the fewest possible bills and coins. A greedy algorithm would do this: At each step, it will take the largest possible bill or coin that does not overshoot
for, eg, To make $6.39, you can choose:
– a $5 bill
– b $1 bill, to make $6
– c 25¢ coining, to make $6.25
– d 10¢ coin, to make $6.35
– e four 1¢ coins, to make $6.39
For US money, the greedy algorithm always gives the optimum solution. However, the greedy algorithm results in a solution, but not in an optimal solution which could lead to its failure.
8. Randomized Algorithms: A randomised algorithm uses a random number at least once during the computation to make a decision.
– Example: In Quicksort, using a random number to choose a pivot or Trying to factor a large prime by selecting random numbers as possible divisors
Therefore, Algorithm rules the world. Every time you hit a search button on Google, the search engine will sift through thousands of webpages to provide you with the content that you are seeking within a fraction of a second. What makes it possible is the underlying “Algorithm” – a set of pre-defined mathematical rules embedded in the software. Take the case of an Automated Teller Machine (ATM). Every time you access the ATM, it enlists for a UID under Aadhaar, or when you book an air ticket or buy something online, you are expanding the range and scope of algorithms – a mathematical concept whose roots date back to 600 AD with the invention of the decimal system.
Every time you use your computer or phone, you are using the algorithms which you can call it as programmes or Apps. What you should know is that an algorithm is nothing but a set of instructions to be followed based on the activity to be performed. Google and Facebook search is now solely based on algorithms though they are more complex than the regular algorithms. Facebook, YouTube, Twitter, and LinkedIn all have gone through a major shift in their algorithm to enhance and customise their followers’ newsfeeds.
This measure of improvising the news feed are based on individual readers preference, “According” to me it has failed significantly. The data scientist and software programmers are missing a critical factor in defining the algorithms, and that is, every individual has a mind that is of his or her own and is programmed in thinking a certain way. This is further broken down between a man and a woman whose thinking capabilities are poles apart. Therefore, every time an individual who defines the algorithm is programming is based on their individual way of thinking and not how others would see the same problem; which is the biggest challenge and a bottleneck that nobody seems to be addressing it.
Let’s take the example of my above statement – Every time I browse through my newsfeed be it in YouTube, Facebook, Twitter, Google, LinkedIn, or Instagram the AI is continuously learning my activities and the kind of news that I am reading. What it is not able to understand is that, even for a moment if I read an article or watch a video of something absolutely irrelevant to me, it assumes, that is the kind of news feeds that I am interested in and throws up a whole load of articles and video content in my news feed based on the assumptions it has made. While the fact is that I am not interested in such information, this is the point the algorithms are failing to learn and they completely mess the news feeds. Instead of making me feel happy they actually make me feel frustrated with this whole new enhancement of customising the news feeds.
To summarise, Algorithms are still defined by humans whose ability of thinking is restricted to that individual and therefore even though the algorithms are built-in to enhance the user experience and be able to provide information by anticipation based on what I am looking for is not helpful given that it still cannot understand my way of thinking. This is where the technology comes to a standstill and is at a nascent stage. The IT giants have to figure out a solution in overcoming this technical challenge in AI. Nevertheless, AI is still going to be the future of this world but in the next 100 years to come.
Image Credit: Pixabay
