Module1

1. Define Big-O and Big-Ω notation with examples?

Big Oh (O) Notation
Definition: The function f(n) = O(g(n)) iff there exists 2 positive constants c and n0
such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0

It is the measure of longest amount of time taken by an algorithm(Worst case).

• It is asymptotically tight upper bound
• O(1) : Computational time is constant
• O(n) : Computational time is linear
• O(n2) : Computational time is quadratic
• O(n3) : Computational time is cubic
• O(2n) : Computational time is exponential
For example:
Find the O notation of the following function f(n) = 3n + 2

0 ≤ f(n)≤ c g(n) for all n≥n0

Here f(n)= 3n + 2 g(n)=n c=4

3n + 2 ≤ 4 n for all n≥n0

3n + 2 ≤ 4 n

If n=1, LHS=5 , RHS=4, False

If n=2, LHS=8 , RHS=8, True
If n=3, LHS=11 , RHS=12, True
If n=4, LHS=14 , RHS=16, True

The above equation is True when n ≥ 2

Therefore n0=2

f(n) = 3n + 2

0 ≤ f(n)≤ c g(n) for all n≥n0

Here f(n)= 3n + 2 g(n)=n c=4 n0=2

3n + 2 ≤ 4 n for all n≥2

Therefore f(n)= O(g(n))

3n + 2= O(n)

Omega (Ω) Notation Definition: The function f(n) = Ω (g(n)) iff there exists 2
positive constant c and n0 such that f(n) ≥ c g(n) ≥ 0 for all n ≥ n0

• It is the measure of smallest amount of time taken by an algorithm(Best case)

• It is asymptotically tight lower bound
For example: Find the Ω notation of the following function
f(n) = 3n + 6n2 + 3n
f(n) ≥ c g(n) ≥ 0 for all n ≥ n0
Here f(n) = 3n + 6n2 + 3n g(n)= 3n c=1

3n + 6n2 + 3n ≥ 1 x 3n for all n ≥ n0

3n + 6n2 + 3n ≥ 1 x 3n

If n=1: LHS=12 RHS=3 True

If n=2: LHS=39 RHS=9 True

This equation is true if n ≥ 1

 Therefore n0 = 1
f(n) = 3n + 6n2 + 3n
f(n) ≥ c g(n) ≥ 0 for all n ≥ n0
Here f(n) = 3n + 6n2 + 3n g(n)= 3n c=1 n0=1

3n + 6n2 + 3n ≥ 1 x 3n for all n ≥ 1

Therefore f(n) = Ω(g(n))

3n + 6n2 + 3n = Ω(3n)

2. Explain how Divide-and-Conquer increases efficiency of sorting

algorithms?
Divide-and-Conquer and Sorting Efficiency
Divide-and-Conquer (D&C) is a powerful algorithm design strategy that improves
efficiency by breaking a problem into smaller subproblems, solving them
recursively, and combining their results.
Sorting algorithms like Merge Sort and Quick Sort use this technique to achieve
better performance than simple algorithms like Bubble Sort or Insertion Sort.

1. Breaking the problem into smaller subproblems

D&C divides an array of size n into two smaller arrays of size n/2.
Smaller problems are easier and faster to solve.
Example:
Merge sort splits an array until each sub-array contains one element (which is already
sorted).

2. Solving subproblems recursively

Each half is sorted independently using the same sorting algorithm.
Since each recursive call handles a smaller input, the total work reduces significantly.
This decreases sorting time from O(n²) (simple sorts) to O(n log n) in most cases.

3. Efficient Combination of Results

After solving subproblems, results are merged or rearranged efficiently:
Merge Sort
• Merging two sorted halves takes O(n) time.
• Since there are log n levels of division, total time = O(n log n).
Quick Sort
• Partitioning around a pivot is O(n).
• Balanced partitions reduce height of recursion tree to log n, giving O(n log n)
average performance.

4. Reduction in recursion depth

 Divide-and-Conquer ensures the recursion depth is log n (in average/best cases)
instead of n.
This reduces total work dramatically compared to algorithms that scan the list
repeatedly.

5. Better performance on large datasets

Simple algorithms (Bubble, Selection, Insertion) repeatedly compare all elements →
O(n²).
D&C sorts efficiently even for very large values of n, because it organizes the work
into multiple levels of decreasing size.

6. Parallelism
Divide-and-Conquer naturally supports parallel execution:
Two halves of the array can be sorted simultaneously by two processors.
This further increases speed on modern systems.

7. Balanced Work Distribution

At each level of the D&C recursion tree:
 Total work = O(n)
 Number of levels = log n
Therefore:
Total time = O(n log n)
This is significantly better than O(n²) for large inputs.
3. Solve the recurrence relations
a) T(n) = T(n/2) + c , T(1)=1

b) T(n) = T(n−1) + n
4. Write Quick Sort algorithm and illustrate for 45,77,23,1,90,67,19,56
5. Solve T(n) = 2T(n/2) + 1, T(1)=1

6. Quicksort worst-case is O(n²). Justify.

Why Quicksort Worst-Case is O(n²)
Quicksort is a Divide-and-Conquer sorting algorithm.
Its running time depends entirely on how well the pivot divides the array.
1. Ideal Case (Balanced Partitioning)
 Pivot splits the list roughly into two equal halves
 Recurrence: T(n) = 2T(n/2) + O(n)
 Leads to: O(n log n) performance.
2. Worst Case (Highly Unbalanced Partitioning)
Worst case occurs when the pivot produces partitions of sizes:
 0 elements on one side
 n−1 elements on the other
This happens when:
 The array is already sorted or reverse sorted.
 Pivot selection is always the first or last element (as shown in many basic
implementations).
 All elements except pivot fall in one partition.
3. Example of Worst Case Partition
If pivot = first element and array is:
 Sorted ascending: 1,2,3,4,5…
 Sorted descending: 9,8,7,6…
Then partition becomes:
 Left partition: empty
 Right partition: n−1 elements
Thus recurrence becomes:
T(n) = T(n − 1) + O(n)
This means:
 T(n) = n + (n−1) + (n−2) + ... + 1
= n(n+1)/2
= O(n²)
4. Why O(n) work at each level?
At each recursive call, Quicksort does:
 Partitioning = O(n)
 Only one subproblem of size n−1 remains
Thus total work forms an arithmetic series:
 n + (n−1) + (n−2) … + 1 = O(n²)

7. Explain Merge Sort and sort 63,24,11,72,59,45,33,26

8. Explain Strassen’s Matrix Multiplication + Time Complexity
Strassen’s Matrix Multiplication Algorithm

Strassen’s algorithm is an improved Divide-and-Conquer method for multiplying two

square matrices.
The normal matrix multiplication takes O(n³) time because it computes 8 multiplications of
submatrices when dividing matrices into 4 blocks.

Strassen reduced the number of multiplications from 8 to 7, making the algorithm faster than
the conventional method.

1. Divide Step

Given two matrices A and B, divide each into four submatrices:

𝐴 𝐴 𝐵 𝐵
𝐴=[ ], 𝐵 = [ ]
𝐴 𝐴 𝐵 𝐵

Each block is of size n/2 × n/2.

2. Strassen’s 7 Products

Instead of computing 8 products like the traditional D&C, Strassen computes the following 7
products (M1–M7):
𝑀 = (𝐴 + 𝐴 )(𝐵 + 𝐵 )
𝑀 = (𝐴 + 𝐴 )𝐵
𝑀 = 𝐴 (𝐵 − 𝐵 )
𝑀 = 𝐴 (𝐵 − 𝐵 )
𝑀 = (𝐴 + 𝐴 )𝐵
𝑀 = (𝐴 − 𝐴 )(𝐵 + 𝐵 )
𝑀 = (𝐴 − 𝐴 )(𝐵 + 𝐵 )
These are computed recursively.

(PDF shows conventional multiplication expansion on p.6–7, forming the base for Strassen’s
improvement.)

DAA_1

3. Combine Step

The final product matrix C is obtained using:

𝐶 =𝑀 +𝑀 −𝑀 +𝑀
𝐶 =𝑀 +𝑀
𝐶 =𝑀 +𝑀
𝐶 =𝑀 −𝑀 +𝑀 +𝑀

4. Why is Strassen Faster?

Traditional D&C requires:

8 recursive multiplications of size n/2 × n/2.
Strassen reduces this to 7 multiplications but uses extra additions/subtractions.

Since multiplication dominates cost, reducing 1 multiplication per level improves complexity.

5. Time Complexity Derivation

The recurrence relation is:

𝑛
𝑇(𝑛) = 7𝑇( ) + 𝑂(𝑛 )
2

• 7 recursive calls (sub-multiplications)

• O(n²) work for matrix additions/subtractions

Using Master Theorem:

𝑇(𝑛) = 𝑂(𝑛 )

Since:

log 7 ≈ 2.81
Final Time Complexity:
.
𝑇(𝑛) = 𝑂(𝑛 )

This is faster than conventional matrix multiplication (O(n³)).

6. Advantages of Strassen’s Algorithm

 Faster asymptotic complexity

 Efficient for large matrices

 Forms the basis for advanced fast matrix multiplication algorithms

7. Limitations

 Requires square matrices of size power of 2

 More numerical instability than standard method

 High constant factors → beneficial mainly for large n

9. Define Time and Space Complexity

Time Complexity (Definition)
Time Complexity of an algorithm is the amount of time taken by the algorithm to execute as
a function of the input size (n).
It measures how fast an algorithm runs.

Key points:

 Expressed using asymptotic notation: O(n), O(n log n), O(n²), etc.
 Counts number of basic operations performed.

 Helps compare efficiency of different algorithms.

Space Complexity (Definition)

Space Complexity of an algorithm is the amount of memory space required for its execution
as a function of input size (n).
It includes:

 Input space
  Auxiliary (extra) space

 Temporary variables, recursion stack, data structures

Key points:

 Expressed using asymptotic notation.

 Examples: O(1), O(n), O(n²) space.

 Measures how much memory an algorithm uses.

Simple Example

 Linear search → Time: O(n), Space: O(1)

 Merge sort → Time: O(n log n), Space: O(n) (extra arrays)

10. Explain control abstraction for divide-and-conquer

Control abstraction is a general template or framework that describes how any Divide-and-
Conquer (D&C) algorithm should be structured.
It hides the low-level details and presents the technique in a clean, reusable form.

D&C algorithms follow three fundamental steps:

1. Divide Step
The problem of size n is divided into one or more smaller subproblems of size n/2, n/3, etc.

Examples:

 Merge Sort divides the array into two halves.

 Quick Sort partitions the array into two subarrays.

2. Conquer Step (Recursive Solution)

Each subproblem is solved recursively using the same algorithm.

If the subproblem becomes small enough (base case), it is solved directly.

3. Combine Step
Solutions of the subproblems are combined to obtain the final answer.

Examples:
  Merge Sort merges two sorted halves.

 Strassen’s algorithm combines 7 matrix products.

Why Control Abstraction is Important?

1. Provides a generic structure for writing D&C algorithms.

2. Separates logic into simple steps → easy to understand, implement, and debug.

3. Allows reuse in many algorithms like Merge Sort, Quick Sort, Binary Search,
Strassen’s multiplication.

4. Helps analyze performance through recurrence relations such as

T(n) = aT(n/b) + f(n) (explained in the PDF).

Examples Using This Abstraction

1. Merge Sort →

o Divide: split array

o Conquer: sort halves

o Combine: merge 2 lists

2. Quick Sort →

o Divide: partition by pivot

o Conquer: sort left and right

o Combine: trivial (in-place)

[Link] various asymptotic notations in algorithms.

Asymptotic Notations

• It is the mathematical notations to represent frequency count.

• 5 types of asymptotic notations

• Big Oh (O)

• Omega (Ω)

• Theta (Ɵ)

• Little Oh (o)

• Little Omega (ω)

 Big Oh (O) Notation Definition: The function f(n) = O(g(n)) iff there exists 2
positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0

It is the measure of longest amount of time taken by an algorithm(Worst case).

• It is asymptotically tight upper bound
• O(1) : Computational time is constant
• O(n) : Computational time is linear
• O(n2) : Computational time is quadratic
• O(n3) : Computational time is cubic
• O(2n) : Computational time is exponential
Omega (Ω) Notation Definition: The function f(n) = Ω (g(n)) iff there exists 2
positive constant c and n0 such that f(n) ≥ c g(n) ≥ 0 for all n ≥ n0

• It is the measure of smallest amount of time taken by an algorithm (Best case)

• It is asymptotically tight lower bound

Theta (Ɵ) Notation Definition: The function f(n) = Ɵ (g(n)) iff there exists 3 positive
constants c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0

• It is the measure of average amount of time taken by an algorithm (Average case)

Little oh (o) Notation Definition: The function f(n) = o(g(n)) iff for any positive

constant c>0, there exists a constant n0>0 such that 0 ≤ f(n) < c g(n) for all n ≥ n0

It is asymptotically loose upper bound

g(n) becomes arbitrarily large relative to f(n) as n approaches infinity

Little Omega (ω) Definition: The function f(n) = ω(g(n)) iff for any positive constant c>0,
there exists a constant n0>0 such that f(n) > c g(n) ≥ 0 for all n ≥ n0

It is asymptotically loose lower bound

f(n) becomes arbitrarily large relative to g(n) as n approaches infinity

[Link] the Quicksort algorithm, sort the following list of numbers using
quicksort algorithm 23, 62 ,27,10,15
[Link] the terms Best Case, Worst Case and Average case complexities?
1. Best Case Complexity

Definition:
Best case complexity is the minimum amount of time (or operations) an algorithm takes to
complete for any input of size n.
It represents the fastest possible performance of the algorithm.
Example:
In Linear Search, if the element is found at the first position,
Time = O(1) (best case).

2. Worst Case Complexity

Definition:
Worst case complexity is the maximum time an algorithm may take to complete for any
input of size n.
It shows the slowest or most time-consuming scenario.

Example:
In Linear Search, if the element is at the last position or not present,
Time = O(n) (worst case).

3. Average Case Complexity

Definition:
Average case complexity is the expected running time of an algorithm, assuming that all
possible inputs of size n are equally likely.
It gives a probabilistic measure of performance.

Example:
In Linear Search, on average the key is found halfway,
Time = O(n) (average case).

Summary Table
Case Meaning Purpose

Best case Minimum running time Shows algorithm’s fastest behavior

Worst case Maximum running time Guarantees performance in the hardest scenario

Average case Expected running time Represents typical performance

[Link] Matrix Multiplication using divide and conquer with an example.

Matrix Multiplication Using Divide and Conquer

Traditional matrix multiplication uses three nested loops and takes O(n³) time for two n × n
matrices.

The Divide-and-Conquer (D&C) strategy improves this by breaking the matrices into
smaller submatrices, solving them recursively, and combining the results.

1. Divide Step

Given two matrices A and B, each of size n × n, we divide them into four submatrices of size
n/2 × n/2:
𝐴 𝐴 𝐵 𝐵
𝐴=[ ], 𝐵 = [ ]
𝐴 𝐴 𝐵 𝐵

This step is shown in the matrix explanation section in your PDF.

DAA_1

2. Conquer Step (Recursive Multiplication)

We compute the following 8 smaller multiplications:

𝐶 =𝐴 𝐵 +𝐴 𝐵
𝐶 =𝐴 𝐵 +𝐴 𝐵
𝐶 =𝐴 𝐵 +𝐴 𝐵
𝐶 =𝐴 𝐵 +𝐴 𝐵

Each multiplication here is itself performed using recursion, until we reach 1×1 matrices
(base case).

This formula is derived in your PDF on pages 6–7.

DAA_1
3. Combine Step

After computing all four blocks 𝐶 , 𝐶 , 𝐶 , 𝐶 , they are combined to form the final product
matrix:
𝐶 𝐶
𝐶=[ ]
𝐶 𝐶

4. Example

Multiply two 2×2 matrices using Divide and Conquer:

1 2 5 6
𝐴=[ ], 𝐵 = [ ]
3 4 7 8

Divide into 1×1 submatrices:

𝐴 = 1, 𝐴 = 2, 𝐴 = 3, 𝐴 =4
𝐵 = 5, 𝐵 = 6, 𝐵 = 7, 𝐵 =8

Compute using formulas:

𝐶 =𝐴 𝐵 +𝐴 𝐵 = 1 × 5 + 2 × 7 = 19
𝐶 =𝐴 𝐵 +𝐴 𝐵 = 1 × 6 + 2 × 8 = 22
𝐶 =𝐴 𝐵 +𝐴 𝐵 = 3 × 5 + 4 × 7 = 43
𝐶 =𝐴 𝐵 +𝐴 𝐵 = 3 × 6 + 4 × 8 = 50

Final Result:
19 22
𝐶=[ ]
43 50

5. Time Complexity

The recurrence relation is:

𝑇(𝑛) = 8𝑇(𝑛/2) + 𝑂(𝑛 )

Using Master theorem:

𝑇(𝑛) = 𝑂(𝑛 )
So, the Divide-and-Conquer version of standard matrix multiplication still has O(n³) time
complexity (Strassen improves this later).

[Link] Merge sort algorithm with an example and analyse the complexities
of the algorithm.
Merge Sort Algorithm

Merge Sort is a Divide-and-Conquer based sorting algorithm.

It works by recursively dividing the list into halves until one element remains, and then
merging the sorted halves to produce the final sorted list.

1. Steps of Merge Sort

A. Divide

Split the array into two halves.

B. Conquer

Recursively apply merge sort to the left and right halves.

C. Combine
Merge the two sorted halves into one sorted array.

This structure matches the control abstraction of Divide-and-Conquer from your PDF (p.14–
16).

DAA_1

2. Merge Sort Algorithm (Pseudocode)

MERGE-SORT(A, left, right)

if left < right:

mid = (left + right) / 2

MERGE-SORT(A, left, mid)

MERGE-SORT(A, mid+1, right)

MERGE(A, left, mid, right)

MERGE(A, left, mid, right)

Create temporary arrays L and R

Compare elements of L and R

Copy smaller elements back into A

3. Example: Sort [63, 24, 11, 72, 59, 45, 33, 26]

Step 1: Divide

Split into two halves:

 Left: [63, 24, 11, 72]

 Right: [59, 45, 33, 26]

Divide further:
Left side breakdown:
→ [63,24] → [63], [24]
→ [11,72] → [11], [72]

Right side breakdown:

→ [59,45] → [59], [45]
→ [33,26] → [33], [26]

Step 2: Conquer (Sort each small list)

 [63], [24] → merge → [24,63]

 [11], [72] → merge → [11,72]

 [59], [45] → merge → [45,59]

 [33], [26] → merge → [26,33]

Step 3: Combine

Left final merge:

[24,63] + [11,72] → [11,24,63,72]

Right final merge:

[45,59] + [26,33] → [26,33,45,59]

Final merge:
[11,24,63,72] + [26,33,45,59]
→ [11,24,26,33,45,59,63,72]
This matches the divide-and-conquer sorting explanation in your PDF.

DAA_1

4. Complexity Analysis

Time Complexity

Merge Sort consistently performs:

 O(n) work at each level for merging

 log n levels (since the list is divided into halves repeatedly)

Thus:

𝑇(𝑛) = 𝑂(𝑛log 𝑛)

This holds for Best, Worst, and Average cases because the division and merging pattern is
always the same.

Space Complexity

Merge Sort requires extra space to store temporary arrays during merging.

Space Complexity = 𝑂(𝑛)

5. Why Merge Sort is Efficient

 Performance is stable at O(n log n) for all cases

 Effective for large datasets

 Ideal for linked lists

 Essential for external sorting (sorting data on disk)

[Link] between space and time complexity?
Difference Between Time Complexity and Space Complexity

Time Complexity Space Complexity

Measures the total time taken by an Measures the total memory used by an
algorithm to run, based on input size n. algorithm during execution.

Indicates how much memory an algorithm

Indicates how fast an algorithm runs.
needs.

Expressed using asymptotic notation such Also expressed using asymptotic notation like
as O(n), O(log n), O(n²). O(1), O(n), O(n²).

Depends mainly on number of operations Depends on memory used for variables, data
(comparisons, loops, recursion depth). structures, recursion stack, and input.

Goal: minimize memory usage, especially

Goal: minimize running time to improve
important for large inputs or limited memory
performance.
systems.

Example: Linear search takes O(n) time. Example: Linear search takes O(1) extra space.

Affects speed of the algorithm. Affects storage requirements of the algorithm.

Short, Direct Definitions

Time Complexity

Amount of time an algorithm takes as a function of input size.

Space Complexity

Amount of memory an algorithm uses as a function of input size.

[Link] merge sort algorithm and give its worst case analysis?
Merge Sort Algorithm

Merge Sort is a Divide-and-Conquer based sorting algorithm.

It works by repeatedly dividing the list into halves, sorting each half, and then merging them.

1. Working of Merge Sort

A) Divide

Split the list into two equal halves until each sub-list contains one element.
B) Conquer

Recursively sort the two halves.

C) Combine

Merge the two sorted halves into one sorted list.

Merging is done by comparing elements and placing the smaller element first.

This follows the same divide–conquer–combine structure discussed in your PDF.

DAA_1

2. Merge Sort Algorithm (Pseudocode)

MERGE-SORT(A, left, right)

if left < right:

mid = (left + right) / 2

MERGE-SORT(A, left, mid)

MERGE-SORT(A, mid + 1, right)

MERGE(A, left, mid, right)

MERGE(A, left, mid, right)

Create temporary arrays L and R

i=j=k=0

While elements remain in both L and R:

copy smaller element to A

 Copy remaining elements (if any)

3. Example of Merge Sort

Consider the list:

[38, 27, 43, 3, 9, 82, 10]

Divide Phase:

 Divide → [38,27,43] and [3,9,82,10]

 Further divide until size = 1

e.g., [38] [27] [43] … etc.

Conquer Phase (Sorting Each Sublist):

 [38] + [27] → [27,38]

 [3] + [9] → [3,9]

 Continue merging…
Combine Phase (Final Merge):

Final sorted list after merging all levels:

[3, 9, 10, 27, 38, 43, 82]

This step-by-step breakdown corresponds to the recursive structure explained in the PDF.

DAA_1

4. Worst-Case Time Complexity Analysis

Recurrence Relation

For merge sort, at each level:

 Dividing the list → O(1)

 Merging the two halves → O(n)

 Number of levels → log n (because list is repeatedly halved)

Thus the recurrence is:

𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑂(𝑛)

This form is similar to the recursive patterns described in your PDF under D&C.
DAA_1

Solving the Recurrence

Using Master Theorem:

 a=2

 b=2

 f(n) = n

 n^{log_b a} = n^{log_2 2} = n

So:

𝑇(𝑛) = Θ(𝑛log 𝑛)

Worst-Case Time Complexity:

\boxed{\text{Worst Case Time Complexity of Merge Sort = O(n \log n)}}

5. Why Worst Case is O(n log n)?

 Merging always takes O(n) time regardless of data order.

 Recursion depth is always log n, because the array is halved every time.

 So even in the worst arrangement of elements, work remains the same.

Unlike Quick Sort, Merge Sort does not degrade to O(n²) in any case.
[Link] f(n)=amnih +am-1nm-1+ ..a1n+a0. Prove that f(n)=O(nm).
Proof that 𝒇(𝒏) = 𝒂𝒎 𝒏𝒎 + 𝒂𝒎 𝟏 𝒏𝒎 𝟏
+ ⋯ + 𝒂𝟏 𝒏 + 𝒂𝟎 = 𝑶(𝒏𝒎 )

Definition (Big-O): 𝑓(𝑛) = 𝑂(𝑔(𝑛))means there exist constants 𝐶 > 0and 𝑛 such that for
all 𝑛 ≥ 𝑛 ,

∣ 𝑓(𝑛) ∣≤ 𝐶 𝑔(𝑛).

We will show such 𝐶, 𝑛 exist with 𝑔(𝑛) = 𝑛 .

Step 1 — take absolute values and use triangle inequality.

∣ 𝑓(𝑛) ∣=∣ 𝑎 𝑛 + 𝑎 𝑛 + ⋯ + 𝑎 𝑛 + 𝑎 ∣≤∣ 𝑎 ∣ 𝑛 +∣ 𝑎 ∣𝑛 + ⋯ +∣ 𝑎

∣ 𝑛+∣ 𝑎 ∣.

Step 2 — bound lower-degree terms by 𝑛 for 𝑛 ≥ 1.

For every 𝑘with 0 ≤ 𝑘 ≤ 𝑚 − 1and 𝑛 ≥ 1we have 𝑛 ≤ 𝑛 . Hence

∣ 𝑎 ∣ 𝑛 ≤∣ 𝑎 ∣ 𝑛 .

Applying this to each term,

∣ 𝑓(𝑛) ∣≤ (∣ 𝑎 ∣ +∣ 𝑎 ∣ + ⋯ +∣ 𝑎 ∣ +∣ 𝑎 ∣) 𝑛 .

Step 3 — choose constants.

Let

𝐶 =∣ 𝑎 ∣ +∣ 𝑎 ∣ + ⋯ +∣ 𝑎 ∣ +∣ 𝑎 ∣.

Choose 𝑛 = 1. Then for all 𝑛 ≥ 𝑛 ,

∣ 𝑓(𝑛) ∣≤ 𝐶 𝑛 .
This exactly matches the Big-O definition, so

𝑓(𝑛) = 𝑂(𝑛 ).

Remark: you may also choose any larger 𝑛 (e.g. to avoid 𝑛 = 0issues) — the proof is
standard and appears in your notes.