Notes

Algorithm
==========

A finite set of instruction that specifies a sequence of operation is to be carried out in order to solve a specific problem or class of problems is called an Algorithm.

An algorithm can be defined as a finite set of steps, which has to be followed while carrying out a particular problem. It is nothing but a process of executing actions step by step.

An algorithm is a computational procedure that takes input as a set of values and results in the output as a set of values by solving the problem.

An algorithm is correct, if, for each input instance, it gets the correct output and gets terminated.

An algorithm can be described by natural language such as English, Computer language, or a hardware language.



Characteristics of Algorithms
=============================
Input: It should externally supply zero or more quantities.
Output: It results in at least one quantity.
Definiteness: Each instruction should be clear and ambiguous.
Finiteness: An algorithm should terminate after executing a finite number of steps.
Independent: An algorithm must be language independent, which means that it should mainly focus on the input and the procedure required to derive the output instead of depending upon the language.


Advantages of an Algorithm
==========================
Effective Communication: Since it is written in a natural language like English, it becomes easy to understand.
Easy Debugging: A well-designed algorithm facilitates easy debugging to detect the logical errors that occurred inside the program.
Easy and Efficient Coding: An algorithm is nothing but a blueprint of a program that helps develop a program.


Disadvantages of an Algorithm
=============================
Developing algorithms for complex problems would be time-consuming and difficult to understand.
It is a challenging task to understand complex logic through algorithms.


Analysis of algorithm
=====================
The analysis is a process of estimating the efficiency of an algorithm. There are two fundamental parameters based on which we can analysis the algorithm:

Space Complexity: The space complexity can be understood as the amount of space required by an algorithm to run to completion.
Time Complexity: Time complexity is a function of input size n that refers to the amount of time needed by an algorithm to run to completion.

Let's understand it with an example.
In general, if there is a problem P1, then it may have many solutions, such that each of these solutions is regarded as an algorithm. So, there may be many algorithms such as A1, A2, A3, …, An.
Before you implement any algorithm as a program, it is better to find out which among these algorithms are good in terms of time and memory.
It would be best to analyze every algorithm in terms of Time that relates to which one could execute faster and Memory corresponding to which one will take less memory.


Generally, we make three types of analysis, which is as follows:

Worst-case time complexity: For 'n' input size, the worst-case time complexity can be defined as the maximum amount of time needed by an algorithm to complete its execution. Thus, it is nothing but a function defined by the maximum number of steps performed on an instance having an input size of n.

Average case time complexity: For 'n' input size, the average-case time complexity can be defined as the average amount of time needed by an algorithm to complete its execution. Thus, it is nothing but a function defined by the average number of steps performed on an instance having an input size of n.

Best case time complexity: For 'n' input size, the best-case time complexity can be defined as the minimum amount of time needed by an algorithm to complete its execution. Thus, it is nothing but a function defined by the minimum number of steps performed on an instance having an input size of n.

======================================================================================================================================================================


Performance Analysis
====================
Performance analysis of an algorithm depends upon two factors i.e. amount of memory used and amount of time consumed on any CPU. Formally they are notified as complexities in terms of:

Space Complexity.
Time Complexity.


Space Complexity of an algorithm is the amount of memory it needs to run to completion i.e. from start of execution to its termination. Space need by any algorithm is the sum of fixed and variable components.
Therefore the total space requirement of any algorithm 'A' can be provided as

Space(A) = Fixed Components(A) + Variable Components(A)


Example: Space Complexity
=========================
Algorithm Sum(number,size)\ procedure will produce sum of all numbers provided in 'number' list
{
result=0.0;
for count = 1 to size do \will repeat from 1,2,3,4,....size times
result= result + number[count];
return result;
}
Space complexity is Space(Sum) = 3 + n;


Time Complexity of an algorithm(basically when converted to program) is the amount of computer time it needs to run to completion. The time taken by a program is the sum of the compile time and the run/execution time.
The time complexity consist of two components fixed and variable/instance. So, for any algorithm 'A' it is provided as:

Time(A) = Fixed Time(A) + Instance Time(A)

======================================================================================================================================================================

Asymptotic Notation
===================
The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the algorithm. The efficiency is measured with the help of asymptotic notations.
Asymptotic notations are the mathematical notations used to describe the running time of an algorithm.

For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is linear i.e. the best case.
But, when the input array is in reverse condition, the algorithm takes the maximum time to sort the elements i.e. the worst case.
When the input array is neither sorted nor in reverse order, then it takes average time. These durations are denoted using asymptotic notations.

There are mainly three asymptotic notations:
Big-O notation
Omega notation
Theta notation

Big-O Notation (O-notation)
Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives the worst-case complexity of an algorithm.


graph



O(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
The above expression can be described as a function f(n) belongs to the set O(g(n)) if there exists a positive constant c such that it lies between 0 and cg(n), for sufficiently large n.
For any value of n, the running time of an algorithm does not cross the time provided by O(g(n)).
Since it gives the worst-case running time of an algorithm, it is widely used to analyze an algorithm as we are always interested in the worst-case scenario.

Omega Notation (Ω-notation)
Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case complexity of an algorithm.


graph


Ω(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
The above expression can be described as a function f(n) belongs to the set Ω(g(n)) if there exists a positive constant c such that it lies above cg(n), for sufficiently large n.
For any value of n, the minimum time required by the algorithm is given by Omega Ω(g(n)).

Theta Notation (Θ-notation)
Theta notation encloses the function from above and below. Since it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the average-case complexity of an algorithm.


graph


For a function g(n), Θ(g(n)) is given by the relation:
Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0
such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }
The above expression can be described as a function f(n) belongs to the set Θ(g(n)) if there exist positive constants c1 and c2 such that it can be sandwiched between c1g(n) and c2g(n), for sufficiently large n.
If a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n ≥ n0, then f(n) is said to be asymptotically tight bound.

======================================================================================================================================================================

Best, Average And Worst Behaviour
================================

Worst Case Analysis (Usually Done)
In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched is not present in the array. Therefore, the worst case time complexity of linear search would be Θ(n).

Average Case Analysis (Sometimes done)
In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs.

Best Case Analysis (Bogus)
In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location.So time complexity in the best case would be Θ(1)




Ankur Gupta