CMP 318 – ANALYSIS & COMPLEXITY OF ALGORITHMS
LECTURE NOTES
BY
CHARLES OKONJI
OUTLINE
• Overview of Algorithms
• Asymptotic Analysis
• Complexity Classes
• Time and Space Tradeoffs in Algorithms
• Analysis of Recursive Algorithms
• Numerical Algorithms
• Sequential and Binary Search Algorithms
• Sorting Algorithms
• Binary Search Trees
• Hash Tables
• Graphs and its Representation.
ASYMPTOTIC ANALYSIS
• The Efficiency of an algorithm is defined mainly by 2 factors i.e. Space and Time.
• A good algorithm is one that takes less time and less space, yet this is not possible all the time. There is, therefore, a
trade-off between Time and Space. If you want to reduce the time, then space might increase. Similarly, if you want
to reduce the space, then the time may increase. So, you have to compromise with either space or time.
• The time taken by an algorithm also depends on the computing speed of the system that you are using, but we
ignore those external factors and we are only concerned on the number of times a particular statement is being
executed with respect to the input size. Let's say, for executing one statement, the time taken is 1sec, then what is
the time taken for executing n statements? It will take n seconds.
• Recollecting, the Time Complexity is the number of operations an algorithm performs to complete its task with
respect to input size (considering that each operation takes the same amount of time). The algorithm that performs
the task in the smallest number of operations is considered the most efficient one.
• To illustrate, supposing you have one problem and you wrote 3 algorithms for the same problem. You are required to
choose one out of those 3 algorithms. How will you do that?
• One thing you can do is to run all the 3 algorithms on 3 different computers, provide same input, find the time taken
by all the 3 algorithms and choose the one with the least amount of time. Is it ok? No, all the systems might be using
some different processors. So, the processing speed might vary. So, we can't use this approach to find the most
efficient algorithm.
• Another thing that you can do is to run all the 3 algorithms on the same computer, try to find the time taken by the
algorithms and then choose the best. Here, you might also get wrong results because, at the time of execution of a
program, there are other things that are executing along with your program, so you might get the wrong time.
ASYMPTOTIC ANALYSIS
Given two algorithms for a task, how do we find out which one is better?
• One naive way of doing this is – to implement both the algorithms and run the two programs on your computer for
different inputs and see which one takes less time. There are many problems with this approach for the analysis of
algorithms.
• It might be possible that for some inputs, the first algorithm performs better than the second. And for some inputs,
the second performs better. It might also be possible that for some inputs, the first algorithm performs better on
one machine, and the second works better on another machine for some other inputs.
• So, we have seen that we can't judge an algorithm by calculating the time taken during its execution in a particular
system. We need some standard notation to analyze the algorithm. We use Asymptotic notation to analyze any
algorithm and based on that we find the most efficient algorithm. Here in Asymptotic notation, we consider not the
system configuration but rather the order of growth of the input. That is, we try to find how the time or the space
taken by the algorithm will increase/decrease after increasing/decreasing the input size.
• Asymptotic Analysis simply handles the above issues in analyzing algorithms, by evaluating the performance of an
algorithm in terms of input size (we don’t measure the actual running time). Thus, we calculate, how the time (or
space) taken by an algorithm increases with the input size.
• Asymptotic Notation is a way to describe the running time or space complexity of an algorithm based on the input
size. It is commonly used in complexity analysis to describe how an algorithm performs as the size of the input
grows. The 3 most commonly used notations are Big O, Omega, and Theta.
• In general, the choice of asymptotic notation depends on the problem and the specific algorithm used to solve it. It
is also important to note that asymptotic notation does not provide an exact running time or space usage for an
algorithm, but rather a description of how the algorithm scales with respect to input size. It is a useful tool for
comparing the efficiency of different algorithms and for predicting how they will perform on large input sizes.
ASYMPTOTIC ANALYSIS
Asymptotic Notations
• Asymptotic Notations are mathematical tools used to analyze the performance of algorithms by understanding how
their efficiency changes as the input size grows. These notations provide a concise way to express the behavior of an
algorithm’s time or space complexity as the input size approaches infinity.
• Rather than comparing algorithms directly, asymptotic analysis focuses on understanding the relative growth rates
of algorithms’ complexities. It enables comparisons of algorithms’ efficiency by abstracting away machine-specific
constants and implementation details, focusing instead on fundamental trends.
• By using asymptotic notations, we can categorize algorithms based on their worst-case, best-case, or average-case
time or space complexities, thereby providing valuable insights into their efficiencies.
• There are mainly 3 asymptotic notations:
1. Big-O Notation (O-notation)
2. Omega Notation (Ω-notation)
3. Theta Notation (Θ-notation)
ASYMPTOTIC ANALYSIS
Big-O Notation (O-notation)
Big-O notation represents the upper bound of the running time of an algorithm. It gives the worst-case complexity of an
algorithm.
Big-O is the condition that allows an algorithm to complete statement execution in the longest amount of time possible.
o If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exists a positive constant C and n0 such
that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
o It returns the highest possible output value (big-O) for a given input.
o The execution time serves as an upper bound on the algorithm’s time complexity.
Mathematically,
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
For example, Consider the case of Insertion Sort. It takes linear time in the best case and quadratic time in the worst
case. Thus, we can safely say that the time complexity of the Insertion sort is O(n2).
ASYMPTOTIC ANALYSIS
• The Big-O notation is useful when we only have an upper bound on the time complexity of an algorithm. Many times we
easily find an upper bound by simply looking at the algorithm.
Examples:
1. { 100 , log (2000) , 10^4 } belongs to O(1)
2. U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to O(n)
3. U { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to O( n^2)
Note: Here, U represents union, we can write it in these manner because O provides exact or upper bounds .
Example 1: Finding the sum of the first n numbers.
In this example, we have to find the sum of first n numbers. For example, if n = 4, then our output should be 1 + 2 + 3 + 4 = 10.
Let's try various solutions to this code and try to compare all those codes.
O(1) solution
// function taking input "n"
int findSum(int n)
{
return n * (n+1) / 2; // this will take some constant time c1
}
In above code, there is only one statement and it takes constant time for its execution. The basic idea is that if the statement is
taking constant time, then it will take the same amount of time for all the input size and we denote this as O(1) .
ASYMPTOTIC ANALYSIS
Example 2:
Given the function, f(n) = 4.n3+10.n2+5.n+1.
Considering that g(n) = n3
Then, f(n) ≥ 5.g(n) for all the values of n > 2.
Hence, the complexity of f(n) can be represented as O (g (n)), i.e. O (n3).
Omega Notation (Ω-Notation)
• Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case complexity of an
algorithm.
• It is defined as the condition that allows an algorithm to complete statement execution in the shortest amount of time.
• Let g and f be the function from the set of natural numbers to itself. The function f is said to be Ω(g), if there is a constant c > 0 and a
natural number n0 such that c*g(n) ≤ f(n) for all n ≥ n0
Mathematically, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
ASYMPTOTIC ANALYSIS
Examples:
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Ω( n^2)
U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Ω(n)
U { 100 , log (2000) , 10^4 } belongs to Ω(1)
Note: Here, U represents union, we can write it in these manner because Ω provides exact or lower bounds.
Theta Notation (Θ-Notation):
• Theta notation encloses the function from above and below. Since it represents the upper and the lower bound of
the running time of an algorithm, it is used for analyzing the average-case complexity of an algorithm.
ASYMPTOTIC ANALYSIS
Mathematically,
Θ (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}
Note: Θ(g) is a set
• The above expression can be described as 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 requires that f(n) must be non-negative for values of n
greater than n0.
• The execution time serves as both a lower and upper bound on the algorithm’s time complexity.
• It exist as both, most, and least boundaries for a given input value.
• A simple way to get the Theta notation of an expression is to drop low-order terms and ignore leading constants. For
example, Consider the expression 3n3 + 6n2 + 6000 = Θ(n3), the dropping lower order terms is always fine because
there will always be a number(n) after which Θ(n3) has higher values than Θ(n2) irrespective of the constants
involved. For a given function g(n), we denote Θ(g(n)) is following set of functions.
Examples:
{ 100 , log (2000) , 10^4 } belongs to Θ(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Θ(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Θ( n2)
Note: Θ provides exact bounds.
ASYMPTOTIC ANALYSIS
Measurement of Complexity of an Algorithm
Based on the above earlier discussed three notations, there are three (3) cases also used to analyze an algorithm:
1. Worst Case Analysis (Mostly used)
• In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. We must know the
case that causes a maximum number of operations to be executed. For Linear Search, the worst case happens when
the element to be searched (x) is not present in the array. When x is not present, the search() function compares it
with all the elements of arr[] one by one. Therefore, the worst-case time complexity of the linear search would
be O(n).
2. Best Case Analysis (Very Rarely used)
• In the best-case analysis, we calculate the lower bound on the running time of an algorithm. We must know the case
that causes a minimum number of operations to be executed. In the linear search problem, the best case occurs
when x is present at the first location. The number of operations in the best case is constant (not dependent on n).
So time complexity in the best case would be Ω(1)
3. Average Case Analysis (Rarely used)
• In average case analysis, we take all possible inputs and calculate the computing time for all of the inputs. Sum all
the calculated values and divide the sum by the total number of inputs. We must know (or predict) the distribution
of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of x
not being present in the array). So we sum all the cases and divide the sum by (n+1). Following is the value of
average-case time complexity.
Average Case Time = \sum_{i=1}^{n}\frac{\theta (i)}{(n+1)} = \frac{\theta (\frac{(n+1)*(n+2)}{2})}{(n+1)} = \theta (n)
ASYMPTOTIC ANALYSIS
Properties of Asymptotic Notations:
1. General Properties:
If f(n) is O(g(n)) then a*f(n) is also O(g(n)), where a is a constant.
Example:
If f(n) = 2n²+5 is O(n²), then then, 7*f(n) = 7(2n²+5) = 14n²+35 is also O(n²).
Similarly, this property satisfies both Θ and Ω notation. Thus, we can say
If f(n) is Θ(g(n)) then a*f(n) is also Θ(g(n)), where a is a constant.
If f(n) is Ω (g(n)) then a*f(n) is also Ω (g(n)), where a is a constant.
2. Transitive Properties:
If f(n) is O(g(n)) and g(n) is O(h(n)), then f(n) = O(h(n)).
Example:
If f(n) = n, g(n) = n² and h(n)=n³
n is O(n²) and n² is O(n³) then, n is O(n³)
Similarly, this property satisfies both Θ and Ω notation.
We can say,
If f(n) is Θ(g(n)) and g(n) is Θ(h(n)) then f(n) = Θ(h(n)) .
If f(n) is Ω (g(n)) and g(n) is Ω (h(n)) then f(n) = Ω (h(n))
ASYMPTOTIC ANALYSIS
3. Reflexive Properties:
Reflexive properties are always easy to understand after transitive.
If f(n) is given then f(n) is O(f(n)). Since MAXIMUM VALUE OF f(n) will be f(n) ITSELF!
Hence x = f(n) and y = O(f(n) tie themselves in reflexive relation always.
Example:
f(n) = n² ; O(n²) i.e O(f(n))
Similarly, this property satisfies both Θ and Ω notation. Thus, we can say that
If f(n) is given then f(n) is Θ(f(n)).
If f(n) is given then f(n) is Ω (f(n)).
4. Symmetric Properties:
If f(n) is Θ(g(n)) then g(n) is Θ(f(n)).
Example:
If(n) = n² and g(n) = n², then, f(n) = Θ(n²) and g(n) = Θ(n²)
This property only satisfies for Θ notation.
ASYMPTOTIC ANALYSIS
5. Transpose Symmetric Properties:
If f(n) is O(g(n)) then g(n) is Ω (f(n)).
Example:
If(n) = n , g(n) = n², then n is O(n²) and n² is Ω (n)
This property only satisfies O and Ω notations.
6. Some More Properties:
1. If f(n) = O(g(n)) and f(n) = Ω(g(n)) then f(n) = Θ(g(n))
2. If f(n) = O(g(n)) and d(n)=O(e(n)) then f(n) + d(n) = O( max( g(n), e(n) ))
Example:
f(n) = n i.e O(n) and d(n) = n² i.e O(n²), then f(n) + d(n) = n + n² i.e O(n²)
3. If f(n)=O(g(n)) and d(n)=O(e(n)) then f(n) * d(n) = O( g(n) * e(n))
Example:
f(n) = n i.e O(n) and d(n) = n² i.e O(n²), then f(n) * d(n) = n * n² = n³ i.e O(n³)
