08:10
ALGORITHM
- An Algorithm is a
set of finite number of steps to solve any given problem.
- A step-by-step
procedure is followed which defines a set of instructions to be executed in a
certain order to get the desired output.
- An algorithm can
be implemented in any programming language.
Characteristics of Algorithm
- Unambiguous - Algorithm should be clear and
unambiguous. Each of its steps and their inputs/outputs should be clear and
must lead to only one meaning.
- Input - An algorithm should have well-defined inputs.
- Output - An algorithm should have well-defined
outputs, and should match the desired output.
- Finiteness - Algorithms must terminate after a finite
number of steps.
- Feasibility - Should be feasible with the available
resources.
- Independent - An algorithm should have step-by-step
directions, which should be independent of any programming code.
Algorithm Complexity
Space Complexity : The amount of computer memory required during execution of a program.
The space required during execution of a program can be classified into two categories:-
Time complexity
It is the running time of a program which is a function of size of input.
Asymptotic
Analysis
It refers to defining the
mathematical bounding/framing of its run-time performance.- Worst Case - Maximum time required for program execution. It is the upper bound on the running time for any input. Thus, algorithm will never go beyond this time limit. It is expressed by Big Oh notation - O.
- Best Case - Minimum time required for program execution. It is the lower bound on the running time for best possible input. It is used to analyse an algorithm for best input. It is expressed by Omega notation – Ω.
- Average Case - Average time required for program execution. It is the estimate of running time for an average input. It is expressed by Theta notation – θ.
No comments
Post a Comment