Basics of Algorithm Analysis ,big-O notation, notion of time and space complexity:
Analysis of an Algorithm:
Algorithm analysis is the process of evaluating an algorithm's efficiency.
The goal is to predict performance without running the program, so it works efficiently for large inputs.
The two main aspects of algorithm analysis are:
o Time Complexity: This measures the amount of time an algorithm takes to complete, as a function
of the input size (usually denoted as n). It counts the number of "basic operations" (like
comparisons, additions, or memory accesses) instead of actual clock time, which can vary between
computers and programming languages.
o Space Complexity: This measures the amount of memory or storage space an algorithm needs to
run to completion, also as a function of the input size.
Asymptotic Analysis: This is the primary theoretical method used to estimate the efficiency for arbitrarily large inputs.
It focuses on the rate of growth of the resource requirements, ignoring constant factors and lower-order terms that
become insignificant for large input sizes.
Types of Analysis
Algorithms are typically analyzed under three different case scenarios to provide a comprehensive view of their
behavior:
Worst-Case Analysis: Determines the maximum time or space an algorithm will ever take for any input of a
given size n. This provides a critical guarantee that the algorithm will never exceed this time limit.
Best-Case Analysis: Determines the minimum time or space an algorithm will take in optimal input
conditions. This is often less useful in practice.
Average-Case Analysis: Determines the expected time or space for a random input of size n, providing a
more realistic measure of typical performance.
Time Complexity can be calculated by using Two types of methods. They are:
Step Count Method
Asymptotic Notation.
Step Count Method::
The step count method is one of the methods to analyze the Time complexity of an algorithm. In this method, we
count the number of times each instruction is executed. Based on that we will calculate the Time Complexity.
1. Comments and declarations are non-executable statements:Not [Link] = 0
2. Simple statements (assignment, return, simple I/O) usually have a frequency count of 1.
3. Conditional Statements
if condition - executed once.
if block - executed 0 or 1 time.
else block - executed 0 or 1 time.
switch(condition) - condition executed once; matching case executes once.
Nested if / if-else ladder - first condition executes once; inner blocks depend on condition results.
3. Loop Statements
Loops execute based on iteration count
for(i = 0; i ≤ n; i++)
Condition checked (n + 1) times.
Body executed n times
while - executes as long as condition is true.
do-while -executes at least once, condition checked after first execution.
4. Functions
Executed according to number of calls.
If called n times - executed n times.
If never called - executed 0 times.
If called once - count all internal statements once (according to their frequency)
If called n times -multiply internal frequency by n
Example 1::
Example 2::
Example3:
Sum of array elements
Check palindrome array
Total Step Count
T(n)=1+(n/2+1)+n/2+n/2+1
T(n)=3n/2+3
Matrix multiplication
Total Step Count
T(n)=an3+bn2+cn+d
Linear search
Total Step Count
T(n)=1+(n+1)+n+n+1
T(n)=3n+3
Binary search
Total Step Count
T(n)=alogn+b
Bubble sort
Total Step Count
T(n)=an2+bn+c
Asymptotic Notation:
Asymptotic notation in data structures is a mathematical way to express the efficiency of algorithms in terms of input
size
Purpose Of Asymptotic Notation
The primary goal of asymptotic notation is to focus on the dominant term in the runtime function, ignoring constant
factors and lower-order terms. This helps in:
Comparing algorithms efficiently – Instead of calculating the exact runtime, we can compare algorithms
based on how their runtimes grow.
Predicting performance for large inputs – As input size increases, minor details become negligible, and the
overall growth rate becomes more important.
Providing a hardware-independent measure – Since it abstracts machine-dependent factors, it allows fair
comparisons of algorithms across different systems.
For example, consider the following time complexities of two algorithms...
Algorithm 1 : 5n2 + 2n + 1 Algorithm 2 : 10n2 + 8n + 3
Generally, when we analyze an algorithm, we consider the time complexity for larger values of input data (i.e. 'n' value).
In above two time complexities, for larger value of 'n' the term '2n+ 1' in algorithm 1 has least significance than the
term '5n2', and the term '8n + 3' in algorithm 2 has least significance than the term '10n2'.
Here, for larger value of 'n' the value of most significant terms ( 5n2 and 10n2 ) is very larger than the value of least
significant terms ( 2n + 1 and 8n + 3 ). So for larger value of 'n' we ignore the least significant terms to represent overall
time required by an algorithm. In asymptotic notation, we use only the most significant terms to represent the time
complexity of an [Link] though both are O(n²), Algorithm 1 has a smaller constant factor, so it will run faster
for large inputs.
There are mainly three asymptotic notations:
Big-O Notation (O-notation)
Omega Notation (Ω-notation)
Theta Notation (Θ-notation)
Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it gives the worst-case
complexity of an algorithm.
It is the most widely used notation for Asymptotic analysis.
It returns the highest possible output value(big-O) for a given input.
Big-O(Worst Case) It is defined as the condition that allows an algorithm to complete statement execution in the
longest amount of time possible.
when both f(n) and g(n) are given and need to judge whether g(n) can be tight upper bound or not
Problem to find upper bound for f(n)
Solve this stepwise and check
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.
The execution time serves as a lower bound on the algorithm's time complexity.
It is defined as the condition that allows an algorithm to complete statement execution in the shortest amount of
time.
Already done finding upper bound so Now find lower bound??
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.
Theta (Average Case) You add the running times for each possible input combination and take the
average in the average case.
Different functions
For large value of n
Space complexity::
Total amount of computer memory required by an algorithm to complete its execution is called as space complexity of
that algorithm.
For any algorithm, memory is required for the following purposes...
constant
Not constant
Examples::
int square(int a)
{
return a*a;
}
In the above piece of code, it requires 2 bytes of memory to store variable 'a' and another 2 bytes of memory is used
for return [Link] means, totally it requires 4 bytes of memory to complete its execution. And this 4 bytes of memory
is fixed for any input value of 'a'. This space complexity is said to be Constant Space Complexity.
int sum(int A[ ], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
In the above piece of code it requires 'n*2' bytes of memory to store array variable 'a[ ]',2 bytes of memory for integer p
arameter 'n',4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes each),2 bytes of memory for return valu
e. That means, totally it requires '2n+8' bytes of memory to complete its execution. Here, the total amount of memory req
uired depends on the value of 'n'. As 'n' value increases the space required also increases proportionately. This type of sp
ace complexity is said to be Linear Space Complexity.
function fibonacci(n)
{
if (n <= 1)
{ return n; }
else { return fibonacci(n - 1) + fibonacci(n - 2); }
}
The space complexity is determined by the maximum depth of the recursive calls, which affects the height of the call
stack. Each function call adds a new frame to the call stack, consuming memory.
As the factorial function makes recursive calls until it reaches the base case, the maximum depth of the recursive calls
is equal to n. Therefore, the space complexity of the factorial algorithm is O(n), indicating linear space usage.