Scribd
Upload
15 views2 pages

Notes Asymptotics

This document provides lecture notes on asymptotic notations used in the analysis of algorithms, detailing definitions and properties of Big-O, Big-Ω, Big-Θ, Little-o, and Little-ω notations. It emphasizes the importance of these notations for measuring algorithm performance as problem size increases, independent of specific hardware or software. Additionally, it includes informal summaries to aid understanding of these concepts.

Uploaded by

h2641526
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views2 pages

Notes Asymptotics

This document provides lecture notes on asymptotic notations used in the analysis of algorithms, detailing definitions and properties of Big-O, Big-Ω, Big-Θ, Little-o, and Little-ω notations. It emphasizes the importance of these notations for measuring algorithm performance as problem size increases, independent of specific hardware or software. Additionally, it includes informal summaries to aid understanding of these concepts.

Uploaded by

h2641526
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

csce750 — Analysis of Algorithms

Fall 2020 — Lecture Notes: Asymptotic Notations

This document contains slides from the lecture, formatted to be suitable for printing or individ-
ual reading, and with some supplemental explanations added. It is intended as a supplement
to, rather than a replacement for, the lectures themselves — you should not expect the notes to
be self-contained or complete on their own.

1 Asymptotic notations
CLRS 3
In the analysis of algorithms, we are usually interested in how the performance of our algorithm
changes as the problem size increases.

The primary tools for measuring the growth rate of a function that describes the run time of an
algorithm are the asymptotic notations.

This provides a way of studying the algorithms themselves, independent of any specific hardware,
operating system, compiler, programmer, etc.

2 Big-O
O(g(n)) = {f (n) | there exist positive constants c and n0 ,
such that 0 ≤ f (n) ≤ cg(n) for all n ≥ n0 . }

3 Big-Ω
Ω(g(n)) = {f (n) | there exist positive constants c and n0 ,
such that 0 ≤ cg(n) ≤ f (n) for all n ≥ n0 . }

4 Big-Θ
Θ(g(n)) = {f (n) | there exist positive constants c1 , c2 , and n0 ,
such that 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n) for all n ≥ n0 . }

More succinctly: Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

5 Anonymous functions
These notations officially refer to sets of functions, but it’s often useful to use them in larger arith-
metic expressions.
T (n) = O(n2 ) means:

T (n) ∈ O(n2 )

T (n) = 2n2 + O(n) means:

There exists f (n) ∈ O(n) with T (n) = 2n2 + f (n).

csce750 Lecture Notes: Asymptotic Notations 1 of 2


6 Little-o
o(g(n)) = {f (n) | for any positive constant c,
there exists a constant n0 such that 0 ≤ f (n) ≤ cg(n)
for all n ≥ n0 . }

This indicates a loose bound: f (n) = o(g(n)) means f (n) grows strictly slower than g(n).

7 Little-ω
ω(g(n)) = {f (n) | for any positive constant c,
there exists a constant n0 such that 0 ≤ cg(n) ≤ f (n)
for all n ≥ n0 . }

This indicates a loose bound: f (n) = ω(g(n)) means f (n) grows strictly faster than g(n).

8 Little-θ?
9 Limits
For functions that are eventually positive, we can compare asymptotic growth rates using limits.

f (n)
Let L = lim , if that limit exists.
n→∞ g(n)

Then f (n) is in . . .

L ω(g(n))? Ω(g(n))? Θ(g(n))? O(g(n))? o(g(n))?


0 ✗ ✗
(0, ∞) ✗ ✗ ✗
∞ ✗ ✗

10 Informal summary of intuition


• f (n) = O(g(n)) is like a ≤ b.

• f (n) = Ω(g(n)) is like a ≥ b.

• f (n) = Θ(g(n)) is like a = b.

• f (n) = o(g(n)) is like a < b.

• f (n) = ω(g(n)) is like a > b.

csce750 Lecture Notes: Asymptotic Notations 2 of 2

You might also like