CSC 2200 Lecture Notes - Lecture 3: Big O Notation, Asymptotic Analysis
9 views2 pages
Published on 19 Jul 2018
School
Department
Course
Professor
CSC 2200 lecture 3
• Introduction
o In order to solve any problem in computer science we need to write a program
o Before writing any program in a programming language it is always better to write an
informal description of the solution i.e; algorithm.
o In general if we have a problem ‘p’ then we have many solutions i.e; algorithms a1, a2,
a3.........and so on
o Before implementing an algorithm as a program we have to find which among those
algorithms is good in terms of Time and Memory
o Before analyzing an algorithm we have to know the terminology used in algorithms.
• Asymptotic analysis
o Asymptotic analysis of an algorithm refers to defining the mathematical framing of its
run-time performance.
o Using asymptotic analysis, we can very well conclude the best case, average case, and
worst case scenario of an algorithm.
o Usually, the time required by an algorithm falls under three types –
▪ Best Case
• Minimum time required for program execution.
▪ Average Case
• Average time required for program execution.
▪ Worst Case
• Maximum time required for program execution.
o Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm