ACADEMY OF TECHNOLOGY
Department: MCA Semester: 2nd
Paper Name: Data Structure with Python Paper Code: MCAN-201
Power Point Presentation on
Performance Measurement of an Algorithm
Presented by
Name of the Student: University Roll No.: 16971024003.
SRIPARNA MAJUMDER
To fulfil the requirement of Continuous Assessment 1 [CA1] of MCA Course.
ALGORITHM PERFORMANCE
MEASUREMENT
This presentation explores key metrics and
methods. We will cover time and space
complexity. We will also discuss case studies and
optimization.
2
TIME COMPLEXITY: BIG O NOTATION
Definition Usage Graphical Representation
Big O notation describes the Big O is crucial. It helps in
upper bound. It represents evaluating algorithm efficiency.
the worst-case scenario. It does this by focusing on
growth rate.
Example
O(n) means linear time. O(n^2) means quadratic time. These represent
growth relative to input size.
O(g(n)) = { f(n): there exist positive constants c and n such that 0
0
≤ f(n) ≤ cg(n) for all n ≥ n }
0
3
TIME COMPLEXITY: BIG Ω NOTATION
Definition Usage Graphical Representation
Big Omega (Ω) gives the lower This notation is less commonly
bound. It shows the best-case used. It can provide a more
scenario. optimistic perspective.
Example
Ω(1) means constant time. The algorithm is at its
most efficient here.
Ω(g(n)) = { f(n): there exist positive constants c and n 0
such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n }
0
4
TIME COMPLEXITY: BIG Θ NOTATION
Definition Usage Graphical Representation
Big Theta (Θ) gives the tight Θ provides a precise estimate. It
bound. It describes average-case is useful for algorithms with
complexity. consistent performance.
Example
Θ(n log n) is common. It is found in efficient sorting
algorithms.
Θ(g(n)) = { f(n): there exist positive constants c , c and n
1 2 0
such that 0 ≤ c g(n) ≤ f(n) ≤ c g(n) for all n ≥ n }
1 2 0
5
MEASURING TIME COMPLEXITY : CONSIDER
A SIMPLE LOOP:
• Runs n times → O(n)
def example(n):
• Best-case (Ω(n))
for i in range(n):
• Worst-case (O(n))
print(i)
• Average-case (Θ(n))
6
SPACE COMPLEXITY: MEMORY ANALYSIS
Example 1: Constant Space O(1)
Definition def swap(a, b):
temp = a
Space complexity measures memory.
a=b
It is memory usage relative to input size. b = temp
• Uses only a few variables → O(1) space
Importance Example 2: Linear Space O(n)
Efficient algorithms minimize space. def create_list(n):
This is especially important for large datasets. arr = [i for i in range(n)]
return arr
• Uses extra space for list → O(n) space.
Metrics
Auxiliary space is additional space used.
Total space includes input data too.
7
CONCLUSION
Measuring the performance of an algorithm is essential for determining its
efficiency in terms of time and space complexity. By analyzing asymptotic
notations (Big-O, Big-Ω, Big-Θ) and conducting empirical testing, we can
assess how an algorithm behaves with increasing input sizes. Optimizing
performance involves selecting the right data structures, minimizing
unnecessary computations, and reducing memory usage. A well-balanced
algorithm ensures scalability, making it suitable for real-world applications.
Ultimately, performance measurement helps in choosing the best algorithm
for a given problem, leading to faster and more efficient software.
8
REFERENCES
• Fundamentals of Data Structures of C, Ellis Horowitz, Sartaj Sahni, Susan Anderson
freed
• Data Structure and Algorithmic Thinking with Python, Narasimha Karumanchi, Career
Monk Publications.
9
THANK YOU
