CS378: Design and Analysis of Algorithms
Algorithm Analysis
Mr. Salman Ashraf
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Algorithm Analysis
• Algorithm analysis is an important part of computational complexity
theory, which provides theoretical estimation for the required
resources of an algorithm to solve a specific computational problem.
Analysis of algorithms is the determination of the amount of time and
space resources required to execute it.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Why Analysis of Algorithms is important?
• To predict the behavior of an algorithm without implementing it on a
specific computer.
• It is much more convenient to have simple measures for the
efficiency of an algorithm than to implement the algorithm and test
the efficiency every time a certain parameter in the underlying
computer system changes.
• It is impossible to predict the exact behavior of an algorithm. There
are too many influencing factors.
• The analysis is thus only an approximation; it is not perfect.
• More importantly, by analyzing different algorithms, we can compare
them to determine the best one for our purpose.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Algorithm Analysis
Algorithm is a finite sequence of well-defined steps used to solve a
given problem. If the problem is having more than one solution or
algorithm, then the best one is decided by the analysis based on two
factors:
• CPU Time (Time Complexity)
• Main Memory Space (Space Complexity)
Time Complexity of an algorithm can be calculated by using two
methods:
• Posteriori Analysis
• Priori Analysis
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Difference between Posterior and Priori analysis
Posteriori Analysis Priori Analysis
Posteriori analysis is a relative analysis. Priori analysis is an absolute analysis.
It is dependent on language of compiler and type It is independent of language of compiler and
of hardware. types of hardware.
It will give exact answer. It will give approximate answer.
It uses the asymptotic notations to represent
It doesn’t use asymptotic notations to represent
how much time the algorithm will take in order to
the time complexity of an algorithm.
complete its execution.
The time complexity of an algorithm using a The time complexity of an algorithm using a
posteriori analysis differ from system to system. priori analysis is same for every system.
If the time taken by the program is less, then the If the algorithm is running faster, credit goes to
credit will go to compiler and hardware. the programmer.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Example
Let us consider the search problem (searching a given item) in a sorted array.
The solution to above search problem includes:
• Linear Search (order of growth is linear)
• Binary Search (order of growth is logarithmic)
• Example:
– We run the Linear Search on a fast computer A
– And run the Binary Search on a slow computer B
– We pick the constant values for the two computers so that it tells us exactly how long it takes
for the given machine to perform the search in seconds.
• Let’s say the constant for A is 0.2 and the constant for B is 1000, which
means that A is 5000 times more powerful than B.
• For small values of input array size n, the fast computer may take less time.
• But, after a certain value of input array size, the Binary Search will start
taking less time compared to the Linear Search even though the Binary
Search is being run on a slow machine.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Why performance analysis?
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Types of Algorithm Analysis
• Worst case: Define the input for which algorithm takes a long time or
maximum time. In the worst case, calculate the upper bound of an
algorithm. Example: In the linear search when search data is not
present at all, then the worst case occurs.
• Best case: Define the input for which algorithm takes less time or
minimum time. In the best case, calculate the lower bound of an
algorithm. Example: In the linear search when search data is present
at the first location of large data, then the best case occurs.
• Average case: In the average case, take all random inputs and
calculate the computation time for all inputs. And then we divide it by
the total number of inputs.
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Algorithmic Common Runtimes
The common algorithmic runtimes from fastest to slowest are:
• Constant: Θ(1)
• Logarithmic: Θ(log N)
• Linear: Θ(N)
• Polynomial: Θ(N2)
• Exponential: Θ(2N)
• Factorial: Θ(N!)
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Big O Notation (O-notation)
• Worst Case
• Upper Bound
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c.g(n)
for all n ≥ n0 }
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Big Omega Notation (Ω-notation)
• Best Case
• Lower Bound
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ c.g(n) ≤ f(n)
for all n ≥ n0 }
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi
CS378: Design and Analysis of Algorithms
Big Theta Notation (Θ-notation)
• Average Case
• Tight Bound
Θ(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 }
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi