Page 1 - Lesson Note-Algorithmic Efficiency

Idea of Algorithmic Efficiency

Algorithm
A method of solving a problem in such a way that given a particular input the algorithm
produces the desired output.

Program
Its an algorithm that has been encoded into some programming language.

Important
There may be many programs for the same algorithm, depending on the programmer and
the programming language used.

The quality of algorithm depends on many internal and external factors.
Internal factors are:
➢ Time required to run
➢ Memory required to run
External factors are:
➢ Size of the input to the algorithm
➢ Speed of the computer on which it is run
➢ Quality of the compiler
External factors are controllable. Efficiency of the algorithm is determined by the internal
factors.

Computational Complexity

Computation is the algorithm of a problem to be solved and complexity is to determine how
much resources (time and space) required to run the algorithm efficiently.
Algorithms are compared by studying their complexity and it also tells the behaviour of the
algorithm when the size of data increases.
Efficiency of algorithm is determined by time (for execution) and space (during execution)
complexity.

Big O notation
Big O notation is used in Computer Science to describe the performance or complexity of an
algorithm. It tells common orders of growth, with the increase in the size of data. Big O
specifically describes the worst-case scenario, and can be used to describe the execution
time required or the space/memory used by an algorithm.

O(1)
O(1) describes an algorithm that will always execute in the same time (or space) regardless
of the size of the input data set. (Ex. Is first element NULL)