ALGORITHM
- An Algorithm is a finite set of instruction that perform a particular task.
An Algorithm should satisfy following criteria.
- Input: Zero or more quantities are supplied externally.
- Output: At least one quantity is produced.
- Definiteness: Each instruction is clear and unambiguous.
- Finiteness: Algorithm must terminate after few steps.
- Effectiveness: Every instruction must be very basic.
ANALYSIS:
It means determining amount of resources (such as time and space) needed to execute it.
TIME COMPLEXITY:
- Time complexity of an algorithm is basically the execution time of a program.
- Time complexity of an algorithm depends on the number of machine instruction.
SPACE COMPLEXITY:
- Space complexity of an algorithm is basically the amount of computer memory required during program execution.
ASYMTOTIC NOTATION:
- BIG OH(O): f(n) is said to be big oh of g(n) that is f(n)=O(g(n)) iff there exists two positive constants n0 and c such that
F(n)<=cg(n) for all n>n0.
- BIG OMEGA(w): f(n) is said to be big omega of g(n) that is f(n)=w(g(n)) iff there exists two positive constants n0 and c such that
F(n)>=cg(n) for all n>n0.
- THETA(Θ): f(n) is said to be big oh of g(n) that is f(n)=Θ(g(n)) iff there exists two positive constants n0 and c such that
F(n)=cg(n) for all n>n0.
- Worst-case complexity:
It is defined by the maximum number of steps taken on any instance of size n.
- Best-case complexity:
It is defined by the maximum number of steps taken on any instance of size n.
- Average-case complexity:
It is defined by the average number of steps taken on any instance of size n.