CSC 2200 Lecture Notes - Lecture 3: Big O Notation, Asymptotic Analysis

9 views2 pages
Published on 19 Jul 2018
Course
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
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.