ASYMPTOTIC NOTATION

DR. HOSSAM HAWASH

1
ASYMPTOTIC ANALYSIS

 To predict the behavior of an algorithm without implementing it on a specific computer.

 It is much more convenient to have simple measures for the efficiency of an algorithm than to implement the
algorithm and test the efficiency every time a certain parameter in the underlying computer system changes.
 It is impossible to predict the exact behavior of an algorithm. There are too many influencing factors.

 The analysis is thus only an approximation; it is not perfect.

 More importantly, by analyzing different algorithms, we can compare them to determine the best one for our
purpose.

2
ASYMPTOTIC NOTATION

 Definition: The notations we use to describe the asymptotic running time of an algorithm are defined in terms of
functions whose domains are the set of natural numbers {0, 1, 2, ⋯ }.
 Big-O Notation

 Big-Ω Notation

 Big-Θ Notation

3
WHY ASYMPTOTIC NOTATION?

 Abstraction of Complexity

 Independence from Hardware and Implementation Details

 Simplified Comparison of Algorithms

 Scalability Analysis

 Facilitates Design Choices

4
COMMONLY USED RATES OF GROWTH

5
COMMONLY USED RATES OF GROWTH
𝒏
𝟐𝟐

𝒏!

𝟒𝒏

𝟐𝒏

𝒏𝟐

𝒏𝒍𝒐𝒈𝒏

log (𝒏!)

𝟐𝐥𝐨𝐠 𝒏

l𝒐𝒈𝟐 𝒏

√𝒍𝒐𝒈𝒏

Log log n

6
BIG-O NOTATION

 Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants
c and n0 such that
f(n)  cg(n) for n  n0
 We use O-notation to give an upper bound on a function, to within a constant factor.
 Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it gives the worst-case complexity of an
algorithm.
 It is the most widely used notation for Asymptotic analysis.
 It specifies the upper bound of a function.
 The maximum time required by an algorithm or the worst-case time complexity.
 It returns the highest possible output value(big-O) for a given input..
 Big-Oh(Worst Case) It is defined as the condition that allows an algorithm to complete statement execution in the longest amount
of time possible.

7
BIG-O NOTATION

8
BIG-O NOTATION

 EX1: Find upper bound for f(n) = 3n + 8

 Solution: 3n + 8 ≤ 4n, for all n ≥ 8
 ∴ 3n + 8 = O(n) with c = 4 and 𝑛0 = 8

 EX2: Find upper bound for f(n) = 𝑛2 + 1

 Solution: 𝑛2 + 1 ≤ 2𝑛2 , for all n ≥ 1
 ∴ 𝑛2 + 1 = O(𝑛2 ) with c = 2 and 𝑛0 = 1

9
BIG-O NOTATION

 EX3: Find upper bound for f(n) = 𝑛4 + 100 𝑛2 + 50

 Solution: 𝑛4 + 100 𝑛2 + 50 ≤ 2𝑛4 , for all 𝑛0 ≥ 11

 ∴ 𝑛4 + 100 𝑛2 + 50 = O(𝑛4) with c = 2 and 𝑛0 = 11

 EX4: Find upper bound for 𝑓(𝑛) = 2𝑛3 – 2𝑛2

 Solution: 2𝑛3 – 2𝑛2 ≤ 2𝑛3 , for all n ≥ 1

 ∴ 2𝑛3 – 2𝑛2 = O(𝑛3 ) with c = 2 and 𝑛0 = 1

10
BIG-Ω NOTATION

 f(n) is (g(n)) if there is a constant c > 0 and an integer constant n0  1 such that
𝑓(𝑛)  𝑐 • 𝑔(𝑛) 𝑓𝑜𝑟 𝑛  𝑛0
 Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case
complexity of an algorithm.
 The execution time serves as a lower bound on the algorithm’s time complexity.

 It is defined as the condition that allows an algorithm to complete statement execution in the shortest amount of
time.

11
BIG-Ω NOTATION

12
BIG-Ω NOTATION

13
BIG-Θ NOTATION

 f(n) is (g(n)) if there are constants 𝑐1 > 0 and 𝑐2 > 0 and an integer constant n0  1 such that:
𝑐1 • 𝑔(𝑛)  𝑓(𝑛)  𝑐2 ’ • 𝑔(𝑛) 𝑓𝑜𝑟 𝑛  𝑛0
 Theta notation encloses the function from above and below.

 Since it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the
average-case complexity of an algorithm.

14
BIG-Θ NOTATION

15
BIG-Θ NOTATION

16
LINEAR TIME COMPLEXITY O(N)

int search(int arr[], int n, int x)

{
int i;
for (i = 0; i < n; i++) {
if (arr[i] == x)
return i;
}
return -1;
}

17
WHICH OF THE FOLLOWING IS ASYMPTOTICALLY TIGHT

Algorithm Best Case Average Case Worst Case

Selection Sort O(𝑛2) O(𝑛2) O(𝑛2)

Bubble Sort O(n) O(𝑛2) O(𝑛2)

Insertion Sort O(n) O(𝑛2) O(𝑛2)

Tree Sort O(nlogn) O(nlogn) O(𝑛2)

Radix Sort O(dn) O(dn) O(dn)

Merge Sort O(nlogn) O(nlogn) O(nlogn)

Heap Sort O(nlogn) O(nlogn) O(nlogn)

Quick Sort O(nlogn) O(nlogn) O(𝑛2)

Bucket Sort O(n+k) O(n+k) O(𝑛2)

Counting Sort O(n+k) O(n+k) O(n+k)

18
QUADRATIC TIME COMPLEXITY

for (int i = 1; i <= n; i += c) {

for (int j = 1; j <= n; j += c) {
// some O(1) expressions
}
}

for (int i = n; i > 0; i -= c) {

for (int j = i + 1; j <= n; j += c) {
// some O(1) expressions
}
}

19
LOGARITHMIC TIME COMPLEXITY O(LOG N)

for (int i = 1; i <= n; i *= c) {

// some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
// some O(1) expressions
}

20
LOGARITHMIC TIME COMPLEXITY O(LOG N)

// Recursive function
void recurse(int n)
{
if (n <= 0)
return;
else {
// some O(1) expressions
}
recurse(n/c);
// Here c is positive integer constant greater than 1
}

21
LOGARITHMIC TIME COMPLEXITY O(LOG LOG N)

for (int i = 2; i <= n; i = pow(i, c)) {

// some O(1) expressions
}
// Here fun() is sqrt or cuberoot or any other constant root
for (int i = n; i > 1; i = fun(i)) {
// some O(1) expressions
}

22
BINARY SEARCH

23
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo hi
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo hi
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo hi
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo
hi
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo
Ex. Binary search for 33. hi
mid
BINARY SEARCH

Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
Invariant. Algorithm maintains a[lo]  value  a[hi].

Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo
hi
mid
THANKS

33