Design And Analysis of Algorithms
Characteristics of an Algorithm.
1. Input. Can take 0 or more inputs.
2. Output. must produce at least 1 output
3. Finiteness. must terminate in finite time.
4. Definiteness. must be clear and unambiguous.
5. Effectiveness. should take less time and space to execute.
Significance of Algorithms
1. A good algorithm will lead to shorter execution time.
2.
Decidable Problems
> The problem for which efficient algorithm exists.
> Takes polynomial time or less to execute.
Undecidable Problems
>The problem for which no efficient algorithm exists.
>Takes exponential time to execute.
Analysis of Algorithms
>Study of an algorithm’s performance based on time and memory
space consumption.
Priori Analysis Posteriori Analysis
1. Estimation of time and memory 1. Calculation of time and memory
space required by an algorithm before space required by an algorithm after
executing it on the system. executing it on the system.
2. Independent of the programming 2. Dependent on the programming
language. language.
3. Independent of the hardware. 3. Dependent on the hardware.
Growth Rate of Algorithms
>This is the rate at which running time increases as a function of input.
Big O Notation
>Way to describe the performance of an algorithm with respect to the
input size.
> It helps in comparing the number of operations.
.Asymptotically – means after some point. (e.g. f(n) is asymptotically
bigger than g(n) means that after some point in the inputs f(n) is always
bigger than g(n))
F(n) = O(g(n)) – means that g(n) is asymptotically bigger than f(n)
Formal Definition of Big O Notation
Assuming f(n) and g(n) are non-negative functions;
F(n) = O(g(n)) iff f(n) <= c.g(n) for all values n > no and C and no are
constants.
>g(n) is the tight upper bound of f(n)
Common Big O Runtimes
i) O(logn) – log time (binary search)
ii) O(n) – linear time (linear search)
iii) O(nlogn) – quicksort
iv) O(n!) – selection sort
Problems that algorithms may solve
1. Searching problems i.e. binary search
2. Sorting problems. – merge sort, quicksort
3. Pathfinding problems – finding the shortest or optimal path
between two points in a graph i.e. Dijkstra’s algorithm in finding
the shortest route between two cities in a road network.
4. Optimization problems – maximize or minimize a specific objective
under given constraints. i.e. in resource allocation and
investments.
5. Pattern Recognition and Classification – i.e. classifying emails as
spam or not spam
Properties of Asymptotic complexities.
i.) Transitivity –
If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n))
ii.) Reflexivity – a function’s growth rate is always equal to its own
growth rate.
For f(n) = 2n2, it’s trivially true that 2n2 = O(2n2)
iii.) Symmetry – for tight bounds (Θ), the relationship is symmetric.
If f(n) grows at the same rate as g(n), then g(n) grows at the
same rate as f(n).
f(n)=Θ(g(n)), then g(n)=Θ(f(n))
iv.) Complementarity - O (upper bound) and Ω (lower bound) are
complementary properties, and Θ (tight bound) is their
intersection
> f(n) = O(g(n)) means f(n) is asymptotically bounded above by
g(n).
> f(n) = Ω(g(n)) means f(n) is asymptotically bounded below by
g(n).
> f(n) = Θ(g(n)) means f(n) is both O(g(n)) and Ω(g(n)).
Using the complexity notation Theta (Θ), express the following
function in three ways:
T(n) = 8n6 + 3n5 + 2n4 + n3 + n2 + 4n + 10
i.) Canonical Form – representing focusing solely on the dominant
term;
T(n) = Θ(n6)
ii.) Full Expression with Coefficient
T(n) = Θ(8n6)
iii.) Expanded polynomial Approximation – other terms are
considered.
T(n) = Θ(8n6 + lower-order terms.)
Master Method
> is a powerful technique used to solve recurrence relations that arise in
the analysis of divide-and-conquer algorithms.
-It provides a way to determine the time complexity of recursive
algorithms by comparing the function at each level of recursion and
simplifying the recurrence.
Cost of solving the sub-problems recursively
nlogba
Three Cases of the Master Method:
i.) When f(n) is smaller than nlogba
(big O)
-The solution to the recurrence is dominated by the recursive calls and
the overall complexity is:
T(n) = Θ (nlogba)
ii.) When f(n) is the same order as nlogba
-the solution to the recurrence is:
T(n) = Θ (nlogba log n)
iii.) When f(n) is larger than nlogba
(big Omega)
-the solution is:
T(n) = Θ (f(n))
-Regularity condition must be satisfied i.e.
a f(n/b) <= k f(n) for some constant k < 1 and sufficiently large n.
Limitations of Asymptotic Notations.
i.) Ignores Constant factors and lower order terms – which may be
significant for practical performance, especially when input size is small.
ii.) No information on Algorithmic Constants – making it hard to predict
the practical efficiency of algorithms for small or medium-sized
datasets.
iii.) Does not account for hardware and architecture – that may be
relevant in real-world hardware contexts, potentially leading to
misleading conclusions about performance on specific machines.
iv.) Assumes Input Size grows large – making it irrelevant for small
problem sizes or specific problem instances.
v.) Does not Capture practical resource usage – space complexity. One
algorithm may be better in the time space but impractical for memory
space.
vi.) Lack of detailed comparative analysis – notations might mask subtle
differences between algorithms in real-world performance.
Using the RAM model for deriving the time complexity for sorting code.
