Department of CSE
DESIGN AND ANALYSIS OF ALGORITHMS
24CS2203
Topic:
Asymptotic Notations
Session
Session- -33
AIM OF THE SESSION
To familiarize students with the concept of Asymptotic Notations.
INSTRUCTIONAL OBJECTIVES
This Session is designed to:
[Link] :- Asymptotic Notations.
[Link] :- Big-Oh, Theta, Omega notations.
LEARNING OUTCOMES
At the end of this session, you should be able to:
[Link] :- Asymptotic Notations.
[Link] :- Big-Oh, Theta, Omega notations
[Link]:- Analyze the efficiency of Algorithms.
Asymptotic Notations
• Asymptotic notations are mathematical tools used to describe the behavior of
functions, often in terms of time complexity and space complexity in computer
science.
• They provide a way to express the limiting behavior of a function when the
argument tends towards a particular value or infinity.
• There are 5 types of asymptotic notations.
Practical Examples
Example #1: If there are 1,000 books, you may need to check up to 1,000 shelves to
find your book.
The running time will not exceed a linear relationship to the input size, hence O(n).
Example #2: If the book is the first one you check, it doesn't matter how large the
library is.
The best-case time complexity will be constant, i.e., Ω(1).
Example #3: In this case, you eliminate half of the remaining books each time you
check one. The time it takes to find a book grows logarithmically with the number of
books.
The time complexity is logarithmic, i.e., Θ(log n).
Big O Notation (O)
Big O - Complexities
Big O - Complexities
• Constant Time Complexity (O(1)): The algorithm takes the same amount of time regardless of
the input size. It means the number of operations remains constant. Example: accessing a
specific element in an array.
• Logarithmic Time Complexity (O(log n)): The runtime grows logarithmically as the input size
increases. Typically occurs in algorithms that divide the problem into smaller chunks and
process each chunk independently. Example: binary search in a sorted array.
• Linear Time Complexity (O(n)): The runtime increases linearly with the size of the input. Each
additional element in the input contributes proportionally to the time taken. Example: iterating
through an array to find a specific element.
Big O - Complexities
• Quadratic Time Complexity (O(n^2)): The runtime is proportional to the square of the input size.
This often occurs with nested loops where each loop iterates over the entire input. Example:
nested loops to compare all pairs of elements in an array.
• Exponential Time Complexity (O(2^n)): The runtime doubles with each addition to the input
size. These algorithms multiply and can become impractical for large inputs. Example:
generating all subsets of a set using recursion.
• Factorial Time Complexity (O(n!)): A naive approach would be to try every possible
permutation resulting in an O(n!) time complexity. For example, the traveling salesman
problem.
Omega Notation (Ω)
Theta Notation (Θ)
Little o Notation (o)
This means that the linear algorithm grows strictly slower than the quadratic one.
Little omega Notation (ω)
When one function grows strictly faster than another, we say that the latter function
grows slower asymptotically compared to the former. Specifically, if a function f(n) is
ω(g(n)), it indicates that as n approaches infinity, g(n) grows asymptotically slower
than f(n).
Visual Summary
• O(g(n)): Upper bound (worst-case)
• Ω(g(n)): Lower bound (best-case)
• Θ(g(n)): Tight bound (average-case)
• o(g(n)): Upper bound (strictly less)
• ω(g(n)): Lower bound (strictly more)
Numerical Comparison
Example
low = 0
for i = 0 to n-1: high = n-1
if array[i] == target: while low <= high:
return i mid = (low + high) // 2
return -1 if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Example
for i = 0 to n-1: for i = 1 to n-1:
for j = 0 to n-i-1: key = array[i]
if array[j] > array[j+1]: j = i-1
swap(array[j], array[j+1]) while j >= 0 and array[j] > key:
array[j+1] = array[j]
j -= 1
array[j+1] = key
SUMMARY
Asymptotic notation provides a simplified way to analyze and compare the
efficiency of algorithms, focusing on their growth rates without being concerned
with constant factors and lower-order terms.
Asymptotic notations are mathematical tools to express the time complexity of
algorithms for asymptotic analysis.
SELF-ASSESSMENT
SELF-ASSESSMENT QUESTIONS
QUESTIONS
1.1. ToTomeasure
measureTime
Timecomplexity
complexityofofan
analgorithm
algorithmBig
BigOOnotation
notationisisused
usedwhich?
which?
[Link]
Thenumber
numberofofexecutions
executionsgrows
growsextremely
extremelyquickly
quicklyasasthe
thesize
sizeofofthe
theinput
inputincreases
increases
TERMINAL QUESTIONS
1. What does it mean when we say that an algorithm X is asymptotically more
efficient than Y?
2. Find upper bound of running time of a cubic function f(n) = 2n3 + 4n + 5.?
3. Write the asymptotic notations use. for best case ,average case and worst
case analysis of algorithms.
REFERENCES FOR FURTHER LEARNING OF THE SESSION
Text Books :
1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, “Fundamentals of
ComputerAlgorithms”, 2nd Edition, University Press, 2008.
2. Cormen, Leizerson &Rivest, “Introduction toalgorithms”, 3rd Edition, Prentice-Hall, 2002.
3. Jon Kleinberg and Eva Tardos, “Algorithm Design”,Pearson Education, 2006.
Reference Books :
1. Robert Sedgewick and Kevin wayne , “Algorithms”, 4th edition, Addison WesleyProf.,(2011).
2. Anny Levitin, “Introduction to Design and Analysis of Algorithms”, 2rd Edition,
PersonEducation Press. (2007).
3. Michael [Link] and Roberto Tamassia, Algorithm Design: Foundations,Analysis and
Internet Examples, Second Edition, Wiley-India, (2006).
4. Steven S. Skiena, “The AlgorithmDesign Manual”, Second Edition, Springer, (2008)
MOOCS :
1. [Link]
[Link]://[Link]/learn/dynamic-programming-greedy-algorithms#modules
THANK YOU