# 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