Algorithm Analysis
Introduction to Algorithm
• In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-
implementable instructions, typically to solve a class of problems or to perform a computation. A
stem by step Procedure.
• Algorithms are unambiguous specifications for performing calculation, data processing, automated
reasoning, and other tasks.
• Will accept Zero or more input, but generate at least one output.
• Every instruction in algo should be effective
Problem Solving Cycle
• Problem Definition: Understand Problem
• Constraints & Conditions: Understand constraints if any
• Design Strategies (Algorithmic Strategy)
• Express & Develop the algo
• Validation (Dry run)
• Analysis (Space and Time analysis)
• Coding
• Testing & Debugging
• Installation
• Maintenance
Need for Analysis
• What parameters can be considered for comparison between cars?
• We do analysis of algorithm to do a performance comparison between different algorithm to figure
out which one is best possible option. Following are the parameters which can be considered while
analysis of an algorithm
• Time
• Space
• Bandwidth
• Register
• Battery power
Types of Analysis
Aspect Experimental (A Posteriori) Analysis Apriori (Asymptotic) Analysis
Performed after code implementation and
Timing Done before implementation, purely theoretical.
execution.
Result Type Measures actual time or space usage. Estimates time or space complexity.
Influencing
Affected by hardware, software, environment, etc. Independent of hardware or software factors.
Factors
Accuracy Provides exact, real-world results. Provides approximate, theoretical results.
Useful for analysing algorithm efficiency for large
Use Case Useful for real-world performance comparison.
inputs.
Asymptotic Notations
• Asymptotic notations are Abstract notation for describing the behavior of algorithm and determine the rate of
growth of a function.
• Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic
analysis.
• The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on
machine specific constants, and doesn’t require algorithms to be implemented and time taken by programs to
be compared.
Asymptotic Notations
• Asymptotic notations are Abstract notation for describing the behavior of algorithm and determine the rate of
growth of a function.
• Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic
analysis.
• The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on
machine specific constants, and doesn’t require algorithms to be implemented and time taken by programs to
be compared.
Big O Notation
• The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.
• The Big O notation is useful when we only have upper bound on time complexity of an algorithm.
• Many times, we easily find an upper bound by simply looking at the algorithm.
• O(g(n)) = {f(n): there exist positive constants C and N0 such that 0 <= f(n) <= C*G(n) for all N >= N0}
Ω Notation
• Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an
asymptotic lower bound.
• Ω Notation can be useful when we have lower bound on time complexity of an algorithm.
• For a given function g(n), we denote by Ω(g(n)) the set of functions.
• Ω (g(n)) = {f(n): there exist positive constants c and n0 such that 0 <= c*g(n) <= f(n) for all n >= n0}.
Theta Notation
• Θ Notation: The theta notation bounds a function from above and below, so it defines exact
asymptotic behaviour.
• For a given function g(n), we denote Θ(g(n)) is following set of functions.
Θ(g(n)) = {f(n): there exist positive constants C1, C2 and n0 such that 0 <= C1*g(n) <= f(n) <=
C2*g(n) for all n >= n0}
The above definition means, if f(n) is theta of g(n), then the value f(n) is always between
C1*g(n) and C2*g(n) for large values of n (n >= n0).
• The definition of theta also requires that f(n) must be non-negative for values of n greater
than n0.
Types of Analysis
• Worst Case Analysis: 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. It is that i/p class for which
the algo takes maximum time. e.g. quick sort takes maximum time on a sorted i/p array.
• Best Case Analysis: 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. It is that i/p class for which the
algo takes minimum time.
• Average Case Analysis: 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. We must know (or
predict) distribution of cases. Identification of all i/p class I1, I2, I3…Ik. Determine the probability that the algo
take the i/p from the respective i/p class (P1, P2, P3...Pk). Determine the time taken by the algo for each input
class based on the order of magnitude (T1, T2, T3, …..., Tk).
• A(n) = σ =1 ∗
1 2 3 4 5 6
57 12 43 68 26 35
Conclusion
• The average case analysis is not easy to do in most of the practical cases and it is rarely done.
In the average case analysis, we must know (or predict) the mathematical distribution of all
possible inputs.
• Most useful analysis is worst case analysis, as help designers to make reliable system even in
worst case.
Order of magnitude
• For time complexity of an algorithm will use Order of magnitude of a statement
in algorithm.
• Order of magnitude of a statement is number of times the
statement(fundamental operations) is executed while running.
• We have to find the order of magnitude of every statement.
• It is a two-step process
• Find the number of fundamental operations
• Finding the number of times, the fundamental operation executes.
int a = 0, b = 0;----------O(1)
for (i = 0; i < N; i++)----O(n)
{
a = a + 1; ------------O(n)
}
O(n)
• It is a two-step process
• Find the number of fundamental operations
• Finding the number of times, the fundamental operation executes.
int a = 0, b = 0; -----------O(1)
for (i = 0; i < N; i++) -----O(n)
{
a = a + 1; --------------O(n)
} O(n+m)
for (j = 0; j < M; j++) -----O(m)
{
b = b + 1; --------------O(m)
}
int a = 0; (1)
for (i = 0; i < N; i++) -------(n)
{
for (j = N; j > i; j--)----(n2)
{
a = a + i + j;--------(n2)
}
O(n )
}
2
int a = 0, b = 0; -----------O(1)
for (i = 0; i < N; i++) -----O(n)
{
a = a + 1; --------------O(n)
}
2
O(n )
int a = 0; (1)
for (i = 0; i < N; i++) ------(n)
{
for (j = N; j > i; j--)--(n2)
{
a = a + i + j;-------(n2)
}
}
int i = 0;--------O(1)
while (i <= n)----O(n/2)
{
i = i + 2;---O(n/2)
}
O(n)
int a = 0, i = N;----O(1)
while (i > 0)--------O(log2n)
{
a = a + i; ------O(log2n)
i = i / 2; ------O(log2n)
}
O(log2n)
for(int i=0;i<n;) ---O(logkn)
{
i = i * k; ----------O(logkn)
}
O(logkn)