What is Algorithm? Algorithm Basics
Algorithm means “a process or set of rules to be followed in calculations or other problem-solving operations”. Therefore Algorithm refers to a set of rules/instructions that step-by-step define how a work is to be executed upon in order to get the expected results. In mathematics and computer science, an algorithm is a finite sequence of well-defined instructions, typically used to solve a class of specific problems or to perform a computation.Algorithms are used as specifications for performing calculations and data processing.
it must have the following characteristics:
Clear and Unambiguous: Algorithm should be clear and unambiguous. Each of its steps should be clear in all aspects and must lead to only one meaning.
Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs.
Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it should be well-defined as well.
Finite-ness: The algorithm must be finite, i.e. it should not end up in an infinite loops or similar.
Feasible: The algorithm must be simple, generic and practical, such that it can be executed upon with the available resources. It must not contain some future technology, or anything.
Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain instructions that can be implemented in any language, and yet the output will be same, as expected.
Algorithm design refers to a method or a mathematical process for problem-solving and engineering algorithms. The design of algorithms is part of many solution theories of operation research, such as dynamic programming and divide-and-conquer. Techniques for designing and implementing algorithm designs are also called algorithm design patterns,[40] with examples including the template method pattern and the decorator pattern.One of the most important aspects of algorithm design is resource (run-time, memory usage) efficiency; the big O notation is used to describe e.g. an algorithm’s run-time growth as the size of its input increases.
Typical steps in the development of algorithms:
- Problem definition
- Development of a model
- Specification of the algorithm
- Designing an algorithm
- Checking the correctness of the algorithm
- Analysis of algorithm
- Implementation of algorithm
- Program testing
- Documentation preparation
There are various ways to classify algorithms, each with its own merits.
Recursion
A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition (also known as termination condition) matches, which is a method common to functional programming. Iterative algorithms use repetitive constructs like loops and sometimes additional data structures like stacks to solve the given problems.
Logical
An algorithm may be viewed as controlled logical deduction. This notion may be expressed as: Algorithm = logic + control.[74] The logic component expresses the axioms that may be used in the computation and the control component determines the way in which deduction is applied to the axioms.
Deterministic or non-deterministic
Deterministic algorithms solve the problem with exact decision at every step of the algorithm whereas non-deterministic algorithms solve problems via guessing although typical guesses are made more accurate through the use of heuristics.
Serial, parallel or distributed
Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time. Those computers are sometimes called serial computers. An algorithm designed for such an environment is called a serial algorithm, as opposed to parallel algorithms or distributed algorithms. Parallel algorithms take advantage of computer architectures where several processors can work on a problem at the same time, whereas distributed algorithms utilize multiple machines connected with a computer network.
Complexity
See also: Complexity class and Parameterized complexity
Algorithms can be classified by the amount of time they need to complete compared to their input size:
Constant time: if the time needed by the algorithm is the same, regardless of the input size. E.g. an access to an array element.
Logarithmic time: if the time is a logarithmic function of the input size. E.g. binary search algorithm.
Linear time: if the time is proportional to the input size. E.g. the traverse of a list.
Polynomial time: if the time is a power of the input size. E.g. the bubble sort algorithm has quadratic time complexity.
Exponential time: if the time is an exponential function of the input size. E.g. Brute-force search.
Advantages of Algorithms:
- It is easy to understand.
- Algorithm is a step-wise representation of a solution to a given problem.
- In Algorithm the problem is broken down into smaller pieces or steps hence, it is easier for the programmer to convert it into an actual program.
Disadvantages of Algorithms:
Writing an algorithm takes a long time so it is time-consuming.
Branching and Looping statements are difficult to show in Algorithms.
How to Design an Algorithm?
In order to write an algorithm, following things are needed as a pre-requisite:
The problem that is to be solved by this algorithm.
The constraints of the problem that must be considered while solving the problem.
The input to be taken to solve the problem.
The output to be expected when the problem the is solved.
The solution to this problem, in the given constraints.
Then the algorithm is written with the help of above parameters such that it solves the problem.
Example: Consider the example to add three numbers and print the sum.
Step 1: Fulfilling the pre-requisites
Step 2: Designing the algorithm
Step 3: Testing the algorithm by implementing it.
| Big O Notation | Name | Example(s) |
| O(1) | Constant | # Odd or Even number, |
| # Look-up table (on average) | ||
| O(log n) | Logarithmic | # Finding element on sorted array with binary search |
| O(n) | Linear | # Find max element in unsorted array, |
| # Duplicate elements in array with Hash Map | ||
| O(n log n) | Linearithmic | # Sorting elements in array with merge sort |
| O(n2) | Quadratic | # Duplicate elements in array **(naïve)**, |
| # Sorting array with bubble sort | ||
| O(n3) | Cubic | # 3 variables equation solver |
| O(2n) | Exponential | # Find all subsets |
| O(n!) | Factorial | # Find all permutations of a given set/string |
Happy Coding