Introduction to Algorithms and Asymptotic Analysis

Prepared for DSC 314 course at IISER-TVM by Dr. Dhanyamol Antony.

Algorithm: Design
An algorithm is a finite sequence of logically related instructions to solve a computational
problem. Any algorithm must have an input provided by the user and must produce an
output. Computational instructions in the algorithm must involve only basic algebraic
(arithmetic) operations and it should terminate after a finite number of steps. Finally,
any algorithm must involve unambiguous instructions and produce the desired output.
Note: Although the phrase algorithm is associated with computer science, the notion of
computation (algorithm) did exist for many centuries.
The definition of algorithm sparks natural fundamental questions:

• How to design an algorithm for a given problem?

• Is every problem algorithmically solvable? If so, how many algorithms can a problem
have and how to find the efficient one?

We shall address these questions in this lecture. Let us consider an example of finding a
maximum element in an array of size n.

Example: Finding a maximum element in an array

Algo Max-array(A, n)

Max = A[1];
for i = 2 to n do
if (A[i] > Max) then
Max = A[i];
return Max;

Note: The maximum can also be computed by sorting the array in an increasing order
(decreasing order) and picking the last element (first element). There are at least five dif-
ferent algorithms to find a maximum element and therefore, it is natural ask for an efficient
algorithm. This calls for the study of analysis of algorithms.

Types of Algorithm
There are two ways to write an algorithm, namely,

1 Prepared by Dr. Dhanyamol Antony

 • Iterative algorithm

• Recursive algorithm

Iterative Algorithm

Fact(n)

for i = 1 to n
fact = fact * i;
return fact;

Here the factorial is calculated as 1 × 2 × 3 × · · · × n.

Recursive Algorithm

Fact(n)

if n = 1
return 1;
else
return n * Fact(n-1);

Here the factorial is calculated as n × (n − 1) × · · · × 1.

Algorithm: Analysis
Designing an algorithm is not just about solving a problem correctly, but doing so efficiently.
The efficiency of an algorithm is measured in terms of its time and space requirements.
• Time Complexity: How long an algorithm takes to run, as a function of input size.

• Space Complexity: How much memory it consumes.

In practice, we focus more on time than space.

Measuring Efficiency
Algorithm analysis depends critically on the computational model used. For example, the
statement that an algorithm runs in O(n log n) time is only valid under a specific model of
computation. The validity of this statement may not hold if the underlying model changes.
We analyze algorithms independent of hardware by counting the number of basic opera-
tions, such as:

Prepared by Dr. Dhanyamol Antony 2

 • Comparisons (e.g., if A[i] < A[j])

• Assignments (e.g., x = y)

• Swaps or arithmetic operations

Computational Model and Analysis

Before formalizing what we mean by a computational model, let us first explore a concrete
example: the problem of computing Fibonacci numbers. This will help us to analyse how
different models can significantly influence the perceived efficiency of an algorithm.

1 Computing Fibonacci Numbers

The Fibonacci sequence is defined by the recurrence:


0
 i=0
Fi = 1 i=1

Fi−1 + Fi−2 i ≥ 2


Method 1: Naive Recursion A straightforward implementation using the recursive defi-

nition of Fibonacci numbers leads to an exponential number of operations.
The Fibonacci numbers are defined by the recurrence relation:

Fn = Fn−1 + Fn−2 , for n ≥ 2

with initial conditions:

F0 = 0, F1 = 1

Assume a solution of the form Fn = rn . Substituting into the recurrence:

rn = rn−1 + rn−2 ⇒ rn − rn−1 − rn−2 = 0

Divide both sides by rn−2 (assuming r ̸= 0):

r2 − r − 1 = 0

Solve the quadratic equation:

√
2 1± 5
r −r−1=0⇒r =
2

Let √ √
1+ 5 1− 5
ϕ= and ψ =
2 2
3 Prepared by Dr. Dhanyamol Antony
The general solution to the recurrence is:
Fn = Aϕn + Bψ n

Use the initial conditions to solve for A and B:

F0 = 0 = A + B ⇒ B = −A
F1 = 1 = Aϕ + Bψ = A(ϕ − ψ)

1 √ 1 1
A= , ϕ−ψ = 5⇒A= √ , B = −√
ϕ−ψ 5 5
√ !n √ !n !
1 1+ 5 1− 5
Fn = √ −
5 2 2

The total number of additions grows proportionally to the value of Fn , resulting in an

exponential time algorithm, which is highly inefficient and impractical for large values of n.
Method 2: Iterative (Dynamic Programming) Notice that to compute each new term
in the Fibonacci sequence, we only require the previous two terms. By applying the principle
of dynamic programming, we can compute Fi iteratively starting from the base cases
F0 = 0 and F1 = 1, and using the relation Fi = Fi−1 + Fi−2 for i ≥ 2.
This approach performs approximately n additions. Compute F0 , F1 , F2 , . . . , Fn in order,
forming each number by summing the two previous. Running time: θ(n). Given that the
n-th Fibonacci number has at most n bits, it is natural to ask whether a faster algorithm
exists.
Method 3: Matrix Exponentiation (recursive squaring)
Define the transformation matrix:  
1 1
T =
1 0

Then the recurrence can be rewritten in matrix form as:

     
Fn n−1 F1 n−1 1
=T =T
Fn−1 F0 0

Then:  
F Fn
T = n+1
n
for all n ≥ 1.
Fn Fn−1

Base Case: n = 1
     
1 1 1 F2 F1 1 1
T = = = ✓
1 0 F1 F0 1 0

Prepared by Dr. Dhanyamol Antony 4

Inductive Step

Assume the formula holds for n. That is,

 
F Fn
T = n+1
n
Fn Fn−1

Then,
       
n+1 n Fn+1 Fn 1 1 Fn+1 + Fn Fn+1 Fn+2 Fn+1
T =T ·T = · = = ✓
Fn Fn−1 1 0 Fn + Fn−1 Fn Fn+1 Fn

Hence, by induction, the formula holds for all n ≥ 1.

Let us now analyze the time complexity of computing Fn using matrix exponentiation.
To compute T n , we use binary exponentiation (also called exponentiation by squaring), which
works as follows:

• If n = 0, return the identity matrix.

• If n is even, compute T n = (T n/2 )2

• If n is odd, compute T n = T · T n−1

Each recursive step reduces the exponent by half, leading to log2 n steps. Each step involves
multiplying two 2 × 2 matrices, which takes constant time: O(1). Therefore, the total time
complexity is: O(log n). This is a significant improvement over the naive recursive algorithm
or even iterative O(n) solutions.
Although computers come in thousands of variations with differing architectures and internal
organizations, it is most useful to think of them at the level of assembly language. Despite
these architectural differences, assembly-level support is typically quite similar. The main
variations are in the number of registers and the word length of the machine. However,
these differences are generally within a small constant factor—usually just a factor of two—
and are thus asymptotically equivalent.
In summary, we can abstractly model any computer as a machine that supports a basic
instruction set consisting of arithmetic operations, logical operations, and memory access
(including indirect addressing). To keep our discussion general and practical, we avoid the
low-level details of specific instruction sets and assume that any instruction on one machine
can be simulated using a constant number of instructions on another. Since algorithm
analysis typically counts the number of operations, rather than their precise execution times
(which may vary by a constant factor), this abstraction is well justified.
In the uniform cost model, each arithmetic or logical operation is assumed to take constant
time, regardless of the size of the operands. This model is commonly used for problems such
as sorting, selection, merging, and many data structure operations, where we often

5 Prepared by Dr. Dhanyamol Antony

count only the number of comparisons, assuming each takes O(1) time. This is generally
acceptable, as the size of elements in such problems typically does not grow during the
execution of the algorithm.

However, this assumption breaks down for problems where the size of numbers grows rapidly.
n
For example, consider repeatedly squaring the number 2, n times. This produces 22 , a
number requiring 2n bits to represent. Clearly, it is unrealistic to assume such a number can
be written or stored in O(n) time. Thus, for such problems, the uniform cost model does
not realistically capture the true computational cost.

At the other extreme, we have the logarithmic cost model, where the cost of an operation
is proportional to the length (in bits) of the operands. This model is aligned with
physical computation and closely resembles the Turing Machine model, which is widely
used in computational complexity theory.
The most commonly used model in algorithm analysis, however, is a hybrid approach.
We assume that for an input of size n, any operation on operands of size O(log n) takes
constant time, i.e., O(1). This is justified as follows: modern processors are built to perform
arithmetic operations (such as addition, multiplication, division) in a fixed number of
clock cycles, provided the operands fit into a word. Since addressing n memory locations
requires log n bits, it is natural to treat log n-bit words as the unit of computation.

Modern processors typically have 64-bit word sizes, which support addressing up to 264
memory locations—well beyond the needs of most algorithms. Thus, we will generally use the
Random Access Machine (RAM) model, where memory can be accessed in constant
time and arithmetic on word-sized operands takes constant time. However, for problems
involving arbitrary-precision numbers (like the repeated squaring example or large in-
teger multiplication), we will resort to the logarithmic cost model to reflect the true
computational complexity.

As a good practice, when designing an algorithm, you should estimate the maximum
size of numbers involved. If all operands remain within O(log n) bits, it is safe to use the
RAM model.

Input Size

The running time T (n) of an algorithm for a problem with input size n depends on n. T (n)
represents the maximum amount of time (worst case) the algorithm takes for any input of
size n. This gives a guarantee that the algorithm will never take more time than T (n),
regardless of the input. But, how do we fix the input size? A natural parameter for:

• Sorting and other problems on arrays: n is the number of elements in the array - Larger
arrays will take longer to sort.
• Graph algorithms: n = number of vertices, m = number of edges
• Numeric problems: input size = number of digits ≈ logb n

Prepared by Dr. Dhanyamol Antony 6

 • Arithmetic operations such as Addition (with carry), Subtraction (with borrow), Mul-
tiplication, Long division, are performed digit by digit, similar to how we do them
manually.

• Therefore, the time complexity of such operations depends on the number of digits
in the input, not the numeric value itself.

• A number n written in base b has approximately logb n digits.

Order of growth

When comparing time complexity functions T (n) across different problems, it is important to
focus on the order of growth (asymptotics) and ignore constant factors. For example,
consider:
f (n) = n3 and g(n) = 5000n2
Although g(n) has a large constant, f (n) has a higher-order term. For small values of n, we
may observe:
f (n) < g(n)
However, eventually, f (n) will grow faster than g(n). To find the crossover point:

n3 = 5000n2 ⇒ n = 5000

Thus, for n > 5000, we have f (n) > g(n).

What happens in the limit, as n increases? When comparing functions T (n), we focus on
their asymptotic behavior as n → ∞ . Asymptotic complexity describes the behavior of
an algorithm’s running time (or space usage) as the size of the input grows toward infinity.
It gives an upper bound, lower bound, or tight bound on performance, abstracting away
constant factors and lower-order terms. When comparing algorithms, we focus on their
asymptotic behavior — how the runtime function T (n) grows as n becomes large.
There is flexibility in defining what counts as a “basic operation”. Example: Swapping two
variables involves three assignments:

tmp ← x, x ← y, y ← tmp

Thus, number of swaps is 3 times number of assignments. If we count each assignment

separately, the total count changes by a constant factor. As long as we focus on asymptotic
complexity, the exact choice doesn’t affect the overall order of growth.

Worst-Case Complexity

• For each input size n, the worst-case input yields the maximum runtime.

7 Prepared by Dr. Dhanyamol Antony

 • Example: Search for K in an unsorted array A:
i ← 0 while i < n and A[i] ̸= K do
i ← i + 1
if i < n return i
else return -1

• Worst-case: K is not in the array ⇒ scan all n elements.

• Worst-case time complexity is O(n).

• Upper bound for the overall running time. Here worst case is proportional to n for
array size n

Average-Case Complexity
• Worst-case complexity can be too pessimistic.

• Average-case complexity considers expected time over all possible inputs.

• Hard to compute in practice:

– What is the distribution over inputs?

– Are all inputs equally likely?
– Need probability distribution over inputs

Worst-Case vs Average-Case
• Worst-case complexity may not reflect typical performance.

• Average-case complexity is often more informative but also harder to compute.

• A good worst-case upper bound is often practically useful.

• A bad worst case upper bound may be less informative. Here try to classify worst case
inputs to find simpler subclasses that are easier to analyze.

Asymptotic complexity analysis

• We measure time complexity up to an order of magnitude.

• Constant factors are ignored when comparing growth rates.

• We use asymptotic notation to describe how functions grow as input size n increases.

Prepared by Dr. Dhanyamol Antony 8

1. Big O Notation (O(g(n))) – Upper Bound

Definition: A function t(n) is said to be O(g(n)) if there exist constants c > 0 and n0 ≥ 0
such that
t(n) ≤ c · g(n), for all n ≥ n0

• This provides an upper bound on growth.

• It describes the worst-case time complexity.

Example 1:
Consider the function:
t(n) = 100n + 5
=⇒

100n + 5 ≤ 100n + n, for n ≥ 5

= 101n ≤ 101n2
⇒ t(n) ≤ 101n2 for n ≥ 5

So we can choose n0 = 5, c = 101.

Alternatively:

100n + 5 ≤ 100n + 5n = 105n ≤ 105n2 , for n ≥ 1

⇒ t(n) ≤ 105n2 for n ≥ 1

Here, n0 = 1, c = 105 also works.

The constants n0 and c are not unique. Big-O describes an asymptotic upper bound, so
any function that eventually grows faster than t(n) qualifies. Hence, by similar logic, we can
also say:
100n + 5 ∈ O(n)

since:
100n + 5 ≤ 105n, for n ≥ 1

9 Prepared by Dr. Dhanyamol Antony

 Figure 1: Big O Notation : t(n) ≤ c · g(n) for n ≥ n0

Example 2: Consider the function:

t(n) = 100n2 + 20n + 5

To prove t(n) ∈ O(n2 ), we find constants c and n0 such that:

t(n) ≤ c · n2 for all n ≥ n0

=⇒
100n2 + 20n + 5 ≤ 100n2 + 20n2 + 5n2 , for n ≥ 1
= (100 + 20 + 5)n2 = 125n2

Thus,
t(n) ≤ 125n2 for n ≥ 1 ⇒ t(n) ∈ O(n2 )
with constants c = 125, n0 = 1.

• What matters in asymptotic analysis is the dominant term.

• In this case, 100n2 dominates the lower-order terms 20n and the constant 5.
• So even though the full expression includes smaller terms, the function grows like n2
in the limit.

Example 3: Suppose we want to test whether:

f (n) = n3 ∈ O(n2 )

By definition, for f (n) ∈ O(n2 ), there must exist constants c > 0 and n0 ≥ 0 such that:
n3 ≤ c · n2 for all n ≥ n0

Prepared by Dr. Dhanyamol Antony 10

 • Divide both sides by n2 (valid for n > 0):

n3
=n≤c
n2

• But this implies n ≤ c for all large n, which is a contradiction.

• No matter how large c is, n will eventually exceed c as n → ∞.

=⇒ n3 ∈
/ O(n2 )

That is, n3 grows strictly faster than n2 , and cannot be upper bounded by cn2 asymptotically.

Combining Asymptotic Complexities

Suppose:
f1 (n) ∈ O(g1 (n)) and f2 (n) ∈ O(g2 (n))

Then:
f1 (n) + f2 (n) ∈ O(max(g1 (n), g2 (n)))

Proof
By the definition of Big-O, there exist constants c1 , n1 such that:

f1 (n) ≤ c1 · g1 (n), for all n ≥ n1

Similarly, there exist constants c2 , n2 such that:

f2 (n) ≤ c2 · g2 (n), for all n ≥ n2

Let n0 = max(n1 , n2 ). Then for all n ≥ n0 , we have:

f1 (n) + f2 (n) ≤ c1 g1 (n) + c2 g2 (n)

Observe that:
c1 g1 (n) + c2 g2 (n) ≤ (c1 + c2 ) · max(g1 (n), g2 (n))
Hence,
f1 (n) + f2 (n) ≤ C · max(g1 (n), g2 (n)), for C = c1 + c2 , and n ≥ n0
Therefore:
f1 (n) + f2 (n) ∈ O(max(g1 (n), g2 (n)))

• Many algorithms consist of multiple phases.

• Suppose:

11 Prepared by Dr. Dhanyamol Antony

 – Phase A takes O(gA (n)) time
– Phase B takes O(gB (n)) time

• Then the total time is:

O(max(gA (n), gB (n)))

• If an algorithm has multiple phases with different time complexities, the overall com-
plexity is dominated by the slowest (i.e., least efficient) phase.

2. Big Omega Notation (Ω(g(n))) – Lower Bound

Definition: A function t(n) is Ω(g(n)) if there exist constants c > 0 and n0 ≥ 0 such that:

t(n) ≥ c · g(n), for all n ≥ n0

Figure 2: Big Omega Notation: t(n) ≥ c · g(n) for n ≥ n0

Example:
n3 ≥ n2 , ∀n ≥ 1 ⇒ n3 ∈ Ω(n2 )

We know:
n3 ≥ n2 , for all n ≥ 0
So we can choose:
c = 1, n0 = 0 ⇒ n3 ∈ Ω(n2 )

• We establish lower bounds for problems as a whole, not for individual algorithms

• Example:

Prepared by Dr. Dhanyamol Antony 12

 Any comparison-based sorting algorithm requires at least Ω(n log n) compar-
isons in the worst case.

• This means that no matter how clever the algorithm, we cannot beat n log n compar-
isons in the general case.

3. Big Theta Notation (Θ(g(n))) – Tight Bound

Definition: A function t(n) is Θ(g(n)) if there exist constants c1 , c2 > 0 and n0 ≥ 0 such
that:
c1 · g(n) ≤ t(n) ≤ c2 · g(n), for all n ≥ n0

Figure 3: Big Omega Notation: c1 g(n)t(n) ≥ c2 g(n) for n ≥ n0

Example: Consider the function:

n(n − 1)
f (n) =
2

n(n − 1)
f (n) =
2
n2 − n
=
2
n2
≤ , for all n ≥ 0
2

13 Prepared by Dr. Dhanyamol Antony

So: f (n) ≤ 12 n2 for n ≥ 0

1
⇒ f (n) ∈ O(n2 ), with c1 = , n0 = 0, (Upper bound Big-O)
2

n(n − 1) n2 − n
f (n) = =
2 2
2
n n
= −
2 2
n2  n n  n2 n2 n2
≥ − · = − = , for n ≥ 2
2 2 2 2 4 4

So: f (n) ≥ 14 n2 for n ≥ 2

1
⇒ f (n) ∈ Ω(n2 ), with c2 = , n0 = 2, (Lower Bound (Big-Ω))
4
Since:
1 2 1
n ≤ f (n) ≤ n2 , for all n ≥ 2
4 2
We conclude:
n(n − 1)
f (n) = ∈ Θ(n2 )
2
Constants used: c1 = 12 , c2 = 14 , n0 = 2
In summary:

• t(n) = O(g(n)): Upper bound — algorithm will not take more time than g(n) asymp-
totically.

• t(n) = Ω(g(n)): Lower bound — problem requires at least g(n) time.

• t(n) = Θ(g(n)): Tight bound — the algorithm is optimal up to constant factors. i.e.,
it is matching with the upper and lower bounds and hence best possible algorithm has
been found.

Examples of Efficiency
Example 1: Sorting a Large Dataset

• Naive algorithm (e.g., Bubble Sort): O(n2 )

• Efficient algorithm (e.g., Merge Sort): O(n log n)

Prepared by Dr. Dhanyamol Antony 14

 • For n = 109 :

– n2 = 1018 operations ⇒ 300 years

– n log n ≈ 3 × 1010 ops ⇒ 5 minutes

Example 2: Real-Time Video Game

• Problem: Find the closest pair among n = 5 × 105 objects

• Naive algorithm: O(n2 ) ⇒ 42 minutes

• Efficient algorithm: O(n log n) ⇒ fractions of a second

Typical Complexity Classes

• log n — logarithmic

• n — linear

• n log n — linearithmic

• n2 , n3 — polynomial

• 2n , n! — exponential/factorial

Summary
• Analyzing efficiency is critical for algorithm design.

• Input size directly impacts running time.

• Worst-case analysis gives us a strong performance guarantee.

• Average-case complexity is valuable when the input distribution is known.

• f (n) = O(g(n)) means g(n) is an upper bound — useful for worst-case analysis.

• f (n) = Ω(g(n)) means g(n) is a lower bound — often used for problem classes.

• f (n) = Θ(g(n)) means a tight bound — best possible matching upper and lower
bounds.

1. f(n) = 2n + 3
Analyze the asymptotic upper bound of the function f (n) = 2n + 3.
Suppose f (n) = O(n)

15 Prepared by Dr. Dhanyamol Antony

 We aim to find constants c > 0 and n0 ≥ 1 such that:

f (n) = 2n + 3 ≤ c · n ∀n ≥ n0

Observe:
2n + 3 ≤ 10n for all n ≥ 1

Hence, choosing c = 10 and n0 = 1, we conclude:

f (n) = O(n)

Also: f (n) = O(n2 )

Since n ≤ n2 for n ≥ 1, it follows:

2n + 3 ≤ 2n2 + 3n2 = 5n2 ⇒ f (n) = O(n2 )

Although f (n) = O(n2 ) is mathematically correct, it is not the tightest bound. The
tightest upper bound remains O(n), which best reflects the growth rate of f (n).

Hierarchy of Common Asymptotic Classes

√
O(1) < O(log n) < O( n) < O(n) < O(n log n) < O(n2 ) < O(n3 ) < O(2n ) < O(3n ) < O(nn )

Step-count Method and Asymptotic Notation

In this section, we shall look at analysis of algorithms using step count method. Time and
space complexity are calculated using step count method. Some basic assumptions are:

• There is no count for { and }.

• Each basic statement like assignment and return has a count of 1.

• If a basic statement is iterated, then multiply by the number of times the loop is run.

• If a loop statement is iterated n times, it has a count of (n + 1). Here the loop runs n
times for the true case and a check is performed for the loop exit (the false condition),
hence the additional 1 in the count.

Prepared by Dr. Dhanyamol Antony 16

Examples for Step-Count Calculation

1. Sum of elements in an array

Algorithm Sum(a, n)

{
sum = 0;
for i = 1 to n do
sum = sum + a[i];
return sum;
}

Step-count (Time Complexity)

• sum = 0; 1
• for i = 1 to n do n+1
• sum = sum + a[i]; n
• return sum; 1

Total Time Complexity = 2n + 3

Step-count (Space Complexity)

• 1 word for sum

• 1 word each for i and n
• n words for array a[]

Total Space = (n + 3) words

2. Adding two matrices of order m and n

Algorithm Add(a, b, c, m, n)

{
for i = 1 to m do
for j = 1 to n do
c[i,j] = a[i,j] + b[i,j];
}

17 Prepared by Dr. Dhanyamol Antony

Step Count

• Outer loop for i = 1 to m m+1

• Inner loop for j = 1 to n m(n + 1)

• Assignment c[i,j] = a[i,j] + b[i,j] mn

Total number of steps = 2mn + 2m + 2

Note: The first for loop is executed m + 1 times. The first m calls are true calls during
which the inner loop is executed, and the (m + 1)-th call is a false call.

3. Fibonacci series

Algorithm Fibonacci(n)

{
if n <= 1 then
output n
else
f2 = 0;
f1 = 1;
for i = 2 to n do
{
f = f1 + f2;
f2 = f1;
f1 = f;
}
output f
}

Step Count

• if n <= 1 1

• f2 = 0; 1

• f1 = 1; 1

• for i = 2 to n n

• f = f1 + f2; n−1

• f2 = f1; n−1

Prepared by Dr. Dhanyamol Antony 18

 • f1 = f; n−1
• output f 1

Total number of steps = 4n + 1

Note: If n ≤ 1, then the step count is just 2, and it is 4n + 1 otherwise.

4. Recursive sum of elements in an array

Algorithm RecursiveSum(a, n)

{
if n <= 0 then
return 0;
else
return RecursiveSum(a, n-1) + a[n];
}

The step count of two is added at each recursive call: one count for making a recursive call
with (n − 1) size input and the other count is for addition when the recursion bottoms out.
Let the step count of an array of size n be denoted as T (n). Then,

T (n) = 3 + T (n − 1), n>0

T (n) = 2, n≤0

Solving the above recurrence relation yields:

T (n) = 3n + 2

Order of Growth
Order of growth gives a simple characterization of the algorithm’s efficiency by identifying
the relatively significant term in the step count.
For example, for 2n2 + 3n + 1, the order of growth depends on 2n2 .

Properties of Asymptotic Notation

Reflexivity
f (n) = O(f (n)), f (n) = Ω(f (n)), f (n) = Θ(f (n))

19 Prepared by Dr. Dhanyamol Antony

Symmetry
f (n) = Θ(g(n)) ⇐⇒ g(n) = Θ(f (n))

Transitivity
f (n) = O(g(n)) ∧ g(n) = O(h(n)) ⇒ f (n) = O(h(n))

Transpose Symmetry
f (n) = O(g(n)) ⇐⇒ g(n) = Ω(f (n))

Prepared by Dr. Dhanyamol Antony 20