Data Structures & Algorithm Analysis

Comprehensive Study Guide

DATA STRUCTURES AND

ALGORITHM ANALYSIS
Comprehensive Study Guide

Topics Covered:
• Introduction to Data Structures & Algorithms and Their Applications
• Linear vs Non-Linear, Primitive vs Non-Primitive Data Structures
• Built-in Data Types vs Abstract Data Types
• Space Complexity vs Time Complexity
• Computer Programs vs Algorithms
• Algorithm Design Steps, Analysis, and Efficiency Measurement
• Running Time Analysis and Algorithm Comparison
• Asymptotic Notations: Big-O, Omega, and Theta
• Best, Worst, and Average Case Complexity
• Mathematical Proofs and Complexity Analysis
• Finding Largest Number: Algorithm with Complexity Analysis

Page 1 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

1. Data Structure and Algorithm Analysis

1.1 What is a Data Structure?
A data structure is a specialized format for organizing, storing, processing, retrieving, and managing
data in a computer so that it can be accessed and modified efficiently. It defines the relationship
between data elements and the operations that can be performed on the data. Data structures are
fundamental to computer science, as they enable efficient data management and form the
backbone of every software application.
In essence, a data structure is a way of arranging data in a computer's memory so that it can be
used efficiently. Different kinds of data structures are suited to different kinds of problems. Some
data structures are highly specialized for specific tasks, while others—like arrays and linked lists—
are more general.

1.2 What is Algorithm Analysis?

Algorithm analysis is the process of determining the computational complexity of algorithms — the
amount of time, storage, and other resources needed to execute them. The goal is to understand
the efficiency of an algorithm and predict its behavior as the input size grows. Algorithm analysis
helps in:
• Choosing the best algorithm for a specific problem
• Predicting how performance changes with increasing data
• Comparing multiple solutions to determine the most efficient one
• Understanding the trade-offs between time and space
Algorithm analysis typically focuses on two primary resources: time complexity (how long the
algorithm takes) and space complexity (how much memory it uses). These are usually expressed
using asymptotic notations such as Big-O, Omega, and Theta.

1.3 Areas of Wide Application

Data structures and algorithm analysis are foundational across virtually all areas of computer
science and software engineering. The following are major application domains:
Application Area Data Structures Used Algorithm Analysis Benefit
Databases & DBMS B-Trees, Hash Tables, Heaps Efficient query optimization and
indexing
Operating Systems Queues, Stacks, Linked Lists, Process scheduling, memory
Trees management
Networking & Communications Graphs, Trees, Queues Routing protocols, packet
scheduling
Artificial Intelligence Graphs, Trees, Priority Search algorithms, pathfinding
Queues (A*)
Compilers & Interpreters Stacks, Trees, Hash Tables Parsing expressions, syntax
analysis
Web Search Engines Tries, Hash Tables, Graphs Indexing, ranking, retrieval
efficiency

Page 2 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Cryptography & Security Arrays, Hash Tables Encryption, hashing, key

management
Computer Graphics Trees, Graphs, Matrices Rendering, collision detection
Bioinformatics Graphs, Arrays, Trees Gene sequencing, protein
folding
E-commerce & Finance Hash Tables, Heaps, Trees Transaction processing, fraud
detection

Page 3 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

2. Comparisons and Distinctions

2.1 Linear vs Non-Linear Data Structures
Data structures are broadly classified into linear and non-linear types based on how data elements
are organized in memory.
Linear Data Structures
In a linear data structure, data elements are arranged sequentially, one after the other. Every
element has a unique predecessor and a unique successor (except the first and last elements).
They are easy to implement and traverse in a single run.
Examples: Arrays, Linked Lists, Stacks, Queues
Non-Linear Data Structures
In a non-linear data structure, data elements are not arranged sequentially. A single element can
connect to multiple elements, and traversal cannot be done in a single run. They are more complex
but better represent hierarchical or network relationships.
Examples: Trees, Graphs, Heaps
Feature Linear Data Structure Non-Linear Data Structure
Arrangement Sequential / one after another Hierarchical or networked
Traversal Can be done in a single run Requires multiple runs
Memory Utilization Less efficient (may waste space) More memory efficient
Implementation Simpler to implement More complex to implement
Level Single level Multiple levels
Examples Array, Stack, Queue, Linked List Tree, Graph, Heap
Relationship Each element has at most 2 Each element can have multiple
neighbors connections
Use Case Sequential processing, simple data Complex relationships, networks,
hierarchies

Similarities: Both store and organize data; both support insert, delete, and search operations; both
can be implemented in main memory; both are used to solve real-world computational problems
efficiently.

2.2 Primitive vs Non-Primitive Data Structures

Primitive Data Structures
Primitive data structures are the most basic or fundamental types of data structures. They directly
hold a single value and are defined by the programming language itself. They are the building
blocks from which all other data structures are created.
Examples: int, float, char, boolean, double, long

Page 4 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Non-Primitive Data Structures

Non-primitive data structures are derived from primitive data structures and are more complex.
They can store collections of values (including other data structures) and must be explicitly defined
or created by the programmer.
Examples: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs
Feature Primitive Non-Primitive
Definition Predefined by the language User-defined or derived types
Value Storage Stores a single value Stores multiple/grouped values
Memory Fixed, known at compile time Dynamic, varies at runtime
Operations Basic (arithmetic, logical) Complex (insert, delete, search,
traverse)
Dependency Independent Built from primitive types
Examples int, float, char, bool Array, Tree, Graph, Stack

2.3 Built-in Data Types vs Abstract Data Types

Built-in Data Types
Built-in data types (also called primitive or basic data types) are those that are directly supported
and defined by a programming language. They come pre-packaged with the language and have
associated operations defined by the language.
• Integer (int): Stores whole numbers — e.g., 5, -3, 100
• Float/Double: Stores decimal numbers — e.g., 3.14, -0.5
• Character (char): Stores single characters — e.g., 'A', 'z'
• Boolean (bool): Stores true or false values
• String: Sequence of characters (built-in in most languages)
Abstract Data Types (ADT)
An Abstract Data Type (ADT) is a theoretical concept that defines a data type purely by its behavior
(operations and their semantics) rather than by its implementation. An ADT specifies WHAT
operations can be performed, not HOW they are implemented. This provides a layer of abstraction
and encapsulation.
• Stack ADT: push(), pop(), peek(), isEmpty() — can be implemented via array or linked list
• Queue ADT: enqueue(), dequeue(), front(), isEmpty() — multiple implementations possible
• List ADT: insert(), delete(), search(), traverse()
• Dictionary/Map ADT: put(), get(), delete(), contains()
Feature Built-in Data Types Abstract Data Types (ADT)
Definition Defined by programming language Defined by logical behavior/interface
Implementation Implemented by the compiler Implemented by programmer
Focus How data is stored What operations are supported
Abstraction Level Low-level High-level

Page 5 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Examples int, float, char, bool Stack, Queue, List, Map

Flexibility Fixed behavior Flexible — multiple implementations

Page 6 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

2.4 Space Complexity vs Time Complexity

When analyzing algorithms, the two most critical resources to consider are time and space. Both
are analyzed relative to the input size n.
Time Complexity
Time complexity is a measure of the amount of time an algorithm takes to complete as a function of
the length (size) of the input. It counts the number of basic operations (comparisons, assignments,
arithmetic operations) performed. Time complexity is NOT about the actual clock time but about the
number of operations as input grows.
• Constant Time — O(1): Accessing an array element by index
• Logarithmic Time — O(log n): Binary search in a sorted array
• Linear Time — O(n): Traversing all elements of a list
• Linearithmic Time — O(n log n): Merge sort, heap sort
• Quadratic Time — O(n²): Bubble sort, selection sort
• Cubic Time — O(n³): Naive matrix multiplication
• Exponential Time — O(2ⁿ): Solving the Travelling Salesman problem by brute force
Space Complexity
Space complexity is a measure of the amount of memory (space) an algorithm requires as a
function of the input size. It includes both the space needed for input data and any auxiliary space
used by the algorithm during execution (stack frames, temporary variables, data structures).
• Input Space: Memory to store the input data
• Auxiliary Space: Extra/temporary memory used during execution
• Total Space = Input Space + Auxiliary Space
Feature Time Complexity Space Complexity
Definition Time taken by an algorithm to run Memory used by an algorithm to run
Measures Number of basic operations Amount of memory (bytes/units)
Components Loop iterations, comparisons, Input + auxiliary variables + recursion
assignments stack
Trade-off Fast algorithm may use more space Memory-efficient may be slower
Notation Big-O, Omega, Theta Big-O, Omega, Theta
Example O(1) Array element access Iterative algorithm with fixed variables
Example O(n) Linear search traversal Storing n items in an auxiliary array
Example O(n²) Bubble sort comparisons Storing an n×n matrix

Similarity: Both use asymptotic notation. Both are functions of input size n. Both measure resource
consumption of an algorithm.

2.5 Computer Program vs Algorithm

Feature Algorithm Computer Program

Page 7 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Definition Step-by-step logical procedure to Implementation of an algorithm in a

solve a problem programming language
Language Written in natural language or Written in a specific language (C,
pseudocode Java, Python, etc.)
Execution Not directly executable by a Directly executable by a
computer computer/machine
Hardware Hardware independent May be hardware/OS dependent
Dependency
Analysis Can be analyzed theoretically Tested empirically on actual
hardware
Purpose Design and planning phase Execution and deployment phase
Scope High-level abstract solution Low-level concrete solution
Example Steps to sort a list of numbers Bubble sort written in Python code

Page 8 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

3. Algorithm Design and Development

3.1 The Use of Algorithms
An algorithm is at the heart of every computer program and computational process. Algorithms
serve the following purposes:
• Problem Solving: They provide a clear, step-by-step method to transform inputs into desired
outputs
• Efficiency: They allow programmers to choose the most efficient method from multiple
possible approaches
• Reusability: A well-designed algorithm can be implemented in any programming language
• Communication: Algorithms allow clear communication of solution logic between developers
• Optimization: Help identify and eliminate redundant operations
• Correctness: Formal algorithms can be proven correct before implementation
• Automation: Algorithms enable computers to automate complex decision-making processes

3.2 Characteristics of a Good Algorithm

1. Input: Takes zero or more well-defined inputs
2. Output: Produces at least one output
3. Definiteness: Every step must be clearly and unambiguously defined
4. Finiteness: Must terminate after a finite number of steps
5. Effectiveness: Every step must be basic enough to be executed exactly
6. Correctness: Must produce the correct output for all valid inputs
7. Efficiency: Must use optimal time and space resources

3.3 Steps Required to Develop an Algorithm

Developing an algorithm is a systematic process that requires careful planning. The following steps
outline the complete algorithm development lifecycle:
8. Problem Definition and Understanding: Clearly state the problem. Identify inputs, outputs,
and constraints. Understand edge cases and special conditions. Example: 'Find the largest
number in a given list of n integers'
9. Problem Analysis: Break the problem into smaller sub-problems. Identify relationships
between sub-problems. Determine what data is needed. Identify the computational
approach (sorting, searching, dynamic programming, etc.)
10. Algorithm Design: Choose an appropriate design strategy (divide & conquer, greedy,
dynamic programming, backtracking). Write the algorithm in pseudocode or flowchart form.
Define all variables, data structures, and operations.
11. Algorithm Verification (Dry Run): Trace through the algorithm manually with a small test
case. Verify correctness for normal, boundary, and edge cases. Check for off-by-one errors,
infinite loops, and incorrect conditions.
12. Complexity Analysis: Analyze time complexity — count operations as a function of n.
Analyze space complexity — count memory units used. Express using asymptotic notation
(Big-O, Omega, Theta).
13. Refinement and Optimization: Reduce redundant steps. Optimize loops and conditions.
Consider alternative approaches with better complexity.

Page 9 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

14. Implementation: Translate the algorithm into a programming language. Follow good coding
practices (readability, modularity).
15. Testing and Debugging: Test with various inputs including boundary values. Debug errors.
Compare actual output with expected output.
16. Documentation: Comment the code clearly. Write documentation explaining the algorithm,
its complexity, and usage.
17. Maintenance and Improvement: Review and update as requirements change. Re-optimize if
input sizes or constraints change.

Page 10 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

4. Algorithm Analysis, Efficiency, and Measurement

4.1 What is Algorithm Analysis?
Algorithm analysis is the theoretical study of an algorithm's performance in terms of resource
consumption — primarily time and space — as a function of input size. The goal is to determine
how the algorithm behaves when the input data grows, which helps in predicting scalability and
choosing the best solution.
Algorithm analysis bridges the gap between theoretical computer science and practical
programming. It enables developers to predict whether an algorithm will run in a second, a minute,
or a year when processing large data sets.

4.2 Algorithm Efficiency

The efficiency of an algorithm is a measure of how well the algorithm utilizes computational
resources. It has two dimensions:
• Time Efficiency: How fast does the algorithm run? How does the running time grow with
input size?
• Space Efficiency: How much memory does the algorithm require? Does it grow
proportionally with input size?
An algorithm is considered efficient if it solves a problem within an acceptable time and memory
budget for the expected input sizes. Efficiency is relative — an O(n²) algorithm may be acceptable
for n = 100 but unacceptable for n = 1,000,000.

4.3 How to Measure Algorithm Efficiency

Theoretical (Asymptotic) Analysis
Theoretical analysis involves mathematically counting the number of elementary operations
(comparisons, assignments, arithmetic) as a function of input size n. This approach is independent
of hardware, compiler, and programming language. The result is expressed using asymptotic
notations.
• Count the dominant operation in the algorithm (e.g., comparison in sorting)
• Express its count as a function T(n)
• Simplify to asymptotic class: O(n²), O(n log n), etc.
Empirical (Experimental) Analysis
Empirical analysis involves implementing the algorithm, running it on actual hardware with different
input sizes, and recording the execution time and memory usage. While this approach gives real-
world measurements, results depend on hardware, programming language, compiler optimizations,
and system load.
Step Count Method
In the step count method, each line of code is assigned a cost (number of times it executes). The
total step count is the sum of all line costs. This provides T(n) — the exact number of operations —
from which the asymptotic complexity is derived.

Page 11 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

5. Running Time Analysis and Algorithm Comparison

5.1 What is Running Time Analysis?
Running time analysis is the process of determining the number of operations an algorithm
performs as a function of its input size n. The running time T(n) captures how the execution time
grows — whether linearly, quadratically, logarithmically, or exponentially — as the input size
increases. The analysis focuses on the dominant term that governs growth for large n.

5.2 How to Analyze Running Time

18. Identify Basic Operations: Determine the most frequent, costliest operation — comparisons
in sorting, multiplications in matrix multiplication.
19. Count Operations: Count how many times the basic operation executes as a function of n.
Use mathematical summations for nested loops.
20. Best, Worst, and Average Case: Determine the operation count for all three scenarios.
21. Simplify to Asymptotic Form: Drop lower-order terms and constants. Express as T(n) =
O(f(n)).
Example — Simple Loop Analysis:
for i = 1 to n: sum = sum + i → The basic operation (addition) runs exactly n times, so T(n) = n =
O(n)
Example — Nested Loop Analysis:
for i = 1 to n: for j = 1 to n: sum = sum + 1 → The addition runs n × n = n² times, so T(n) = n² =
O(n²)

5.3 How to Compare Algorithms

When multiple algorithms solve the same problem, we compare them by their asymptotic
complexity classes. The lower the order of the complexity function, the more efficient the algorithm.
Complexity Name Example Algorithm Relative Efficiency
Class
O(1) Constant Array element access Best — Most Efficient
O(log n) Logarithmic Binary Search Excellent
O(n) Linear Linear Search Good
O(n log n) Linearithmic Merge Sort, Heap Sort Good — Near Optimal for
Sorting
O(n²) Quadratic Bubble Sort, Selection Fair — Acceptable for small n
Sort
O(n³) Cubic Matrix Multiplication Poor for large n
(naive)
O(2ⁿ) Exponential Brute-force subsets Very Poor — Infeasible for
large n
O(n!) Factorial Permutation generation Worst — Only feasible for tiny n

Page 12 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Rule of Thumb: When comparing two algorithms, prefer the one with the lower-order complexity for
large n, even if constants are larger. For small n, even an O(n²) algorithm may outperform an O(n
log n) algorithm due to lower constant factors.

Page 13 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

6. Asymptotic Notation
6.1 Why We Use Asymptotic Notation
Asymptotic notation is used to describe the limiting behavior of a function (algorithm's resource
usage) as the input size n approaches infinity. We use asymptotic notation because:
• Hardware Independence: Actual timing depends on CPU speed, compiler, OS. Asymptotic
analysis is universal.
• Input Independence: We want analysis that holds regardless of specific input values.
• Simplicity: It drops constants and lower-order terms, revealing the true growth rate.
• Scalability Prediction: Tells us how the algorithm behaves for very large inputs.
• Algorithm Comparison: Provides a fair, consistent basis for comparing algorithms.
• Mathematical Rigor: Provides formal, provable bounds on algorithm performance.

6.2 Big-O Notation — O(f(n))

Big-O notation describes the UPPER BOUND of an algorithm's running time. It gives the worst-case
growth rate — the maximum time or space an algorithm will ever require.
Formal Definition: f(n) = O(g(n)) if and only if there exist positive constants c and n₀ such that 0 ≤
f(n) ≤ c·g(n) for all n ≥ n₀
Interpretation: f(n) grows no faster than g(n). g(n) is an asymptotic upper bound for f(n).
Example: f(n) = 3n² + 5n + 2 = O(n²) because 3n² + 5n + 2 ≤ 10n² for all n ≥ 1. Here c = 10, n₀ = 1.
• O(1) — Constant: Accessing an array element, hash table lookup
• O(log n) — Logarithmic: Binary search, balanced BST operations
• O(n) — Linear: Linear search, array traversal
• O(n log n) — Linearithmic: Merge sort, heap sort
• O(n²) — Quadratic: Bubble sort, insertion sort (worst case)

6.3 Omega Notation — Ω(f(n))

Omega notation describes the LOWER BOUND of an algorithm's running time. It gives the best-
case growth rate — the minimum time the algorithm will ever require.
Formal Definition: f(n) = Ω(g(n)) if and only if there exist positive constants c and n₀ such that 0 ≤
c·g(n) ≤ f(n) for all n ≥ n₀
Interpretation: f(n) grows at least as fast as g(n). g(n) is an asymptotic lower bound for f(n).
Example: f(n) = 3n² + 5n + 2 = Ω(n²) because 3n² + 5n + 2 ≥ 3n² for all n ≥ 0.
Example: Linear search is Ω(1) — in the best case (element found at position 0), it performs just
one comparison.

6.4 Theta Notation — Θ(f(n))

Theta notation describes the TIGHT BOUND — both upper and lower bound simultaneously. It says
the algorithm's running time grows exactly at the rate of g(n) (up to constant factors).
Formal Definition: f(n) = Θ(g(n)) if and only if there exist positive constants c₁, c₂ and n₀ such that
c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀

Page 14 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Interpretation: Θ(g(n)) means f(n) = O(g(n)) AND f(n) = Ω(g(n)). It is the most precise of the three
notations.
Example: f(n) = 4n² + 2n is Θ(n²) because both 2n² ≤ 4n² + 2n (Omega) and 4n² + 2n ≤ 6n² (Big-O)
hold for large n.
Notation Bound Type Meaning Example Use
Big-O: O(g(n)) Upper Bound f(n) grows NO FASTER Worst-case analysis —
than g(n) guarantees max time
Omega: Ω(g(n)) Lower Bound f(n) grows AT LEAST as Best-case analysis —
fast as g(n) guarantees min time
Theta: Θ(g(n)) Tight Bound f(n) grows EXACTLY as Average/exact case — most
fast as g(n) precise analysis
Little-o: o(g(n)) Strict Upper f(n) grows STRICTLY f(n) is dominated by g(n)
Bound SLOWER than g(n)
Little-omega: ω(g(n)) Strict Lower f(n) grows STRICTLY g(n) is dominated by f(n)
Bound FASTER than g(n)

Page 15 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

7. Best, Worst, and Average Case Complexity

7.1 Definitions and Functions in Algorithm Analysis
For a given algorithm, the running time may vary not only with input size n but also with the specific
arrangement or content of the input. We analyze three scenarios:
Best Case Complexity — B(n)
The best case complexity describes the minimum number of operations an algorithm performs over
all inputs of size n. It represents the most favorable input configuration for the algorithm.
• Denoted: B(n) = Ω(f(n)) — expressed as a lower bound
• Example — Linear Search: The best case is when the target element is at position 0. Only 1
comparison is needed. B(n) = Ω(1)
• Example — Bubble Sort: Even in the best case (sorted array), the algorithm makes n(n-1)/2
comparisons in basic form, though optimized versions achieve O(n)
Note: Best case analysis gives an overly optimistic view and is rarely used for performance
guarantees.
Worst Case Complexity — W(n)
The worst case complexity describes the maximum number of operations an algorithm performs
over all inputs of size n. It represents the most unfavorable input configuration.
• Denoted: W(n) = O(f(n)) — expressed as an upper bound
• Example — Linear Search: The worst case is when the target is at the last position or
absent. All n elements are checked. W(n) = O(n)
• Example — Quick Sort: The worst case is when the pivot is always the smallest or largest
element. W(n) = O(n²)
Importance: Worst case analysis is the most widely used because it provides a guaranteed upper
bound. No matter what the input, the algorithm will never exceed W(n) operations.
Average Case Complexity — A(n)
The average case complexity describes the expected number of operations over all possible inputs
of size n, assuming some probability distribution (usually uniform) over inputs.
• Denoted: A(n) = Θ(f(n)) — tight bound representing typical behavior
• Example — Linear Search: On average, the target is at position n/2. A(n) = Θ(n/2) = Θ(n)
• Example — Quick Sort: With a random pivot, the average case is A(n) = Θ(n log n)
Note: Average case analysis requires probabilistic reasoning and is more complex to compute, but
often gives the most realistic picture of expected performance.
Feature Best Case Worst Case Average Case
Definition Minimum operations Maximum operations Expected operations over
for best input for worst input all inputs
Notation Ω(f(n)) O(f(n)) Θ(f(n))
Practicality Rarely achievable Always guaranteed Most realistic for typical
as upper bound inputs

Page 16 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Linear Search Ω(1) — first element O(n) — last/absent Θ(n/2) = Θ(n)

Binary Search Ω(1) — middle O(log n) — deepest Θ(log n)
element node
Bubble Sort Ω(n) — already O(n²) — reverse Θ(n²)
sorted sorted
Quick Sort Ω(n log n) — O(n²) — sorted input Θ(n log n)
balanced pivots
Usage Shows algorithm can Provides performance Shows typical performance
be fast guarantee

Page 17 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

8. Mathematical Proofs
8.1 Proof: If g(n) = o(f(n)), then f(n) + g(n) = Θ(f(n))
Given: g(n) = o(f(n)) — i.e., g(n) is little-o of f(n)
Required: Prove that f(n) + g(n) = Θ(f(n))
Recall the Definitions:
• Little-o definition: g(n) = o(f(n)) means for every constant c > 0, there exists n₀ such that 0 ≤
g(n) < c·f(n) for all n ≥ n₀. In particular, lim(n→∞) g(n)/f(n) = 0.
• Theta definition: h(n) = Θ(f(n)) means there exist constants c₁ > 0, c₂ > 0, and n₀ such that
c₁·f(n) ≤ h(n) ≤ c₂·f(n) for all n ≥ n₀.
Proof:
We need to show: c₁·f(n) ≤ f(n) + g(n) ≤ c₂·f(n) for some constants c₁, c₂ > 0 and all n ≥ n₀.
Step 1 — Upper Bound (Big-O):
Since g(n) = o(f(n)), taking c = 1 in the little-o definition: there exists n₁ such that g(n) < f(n) for all n
≥ n₁.
Therefore: f(n) + g(n) < f(n) + f(n) = 2·f(n) for all n ≥ n₁.
So f(n) + g(n) = O(f(n)) with constant c₂ = 2.
Step 2 — Lower Bound (Omega):
Since g(n) = o(f(n)), we know that lim(n→∞) g(n)/f(n) = 0, which means g(n)/f(n) → 0. Therefore g(n)
can be negative or positive but is asymptotically smaller.
Assuming f(n) ≥ 0 and g(n) ≥ 0 (non-negative functions), then: f(n) + g(n) ≥ f(n) ≥ 1·f(n).
So f(n) + g(n) = Ω(f(n)) with constant c₁ = 1.
Step 3 — Conclusion:
Since f(n) + g(n) = O(f(n)) [with c₂ = 2] AND f(n) + g(n) = Ω(f(n)) [with c₁ = 1], by definition of Theta:
∴ f(n) + g(n) = Θ(f(n)) ■ QED

8.2 Proof: f(n) = O(g(n)) ⟺ g(n) = Ω(f(n))

This is a bidirectional (if and only if) proof requiring two directions.
Part 1: f(n) = O(g(n)) ⟹ g(n) = Ω(f(n))
Assume f(n) = O(g(n)).
By definition of Big-O: ∃ constants c > 0 and n₀ ≥ 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.
Dividing both sides of f(n) ≤ c·g(n) by c (since c > 0):
(1/c)·f(n) ≤ g(n), or equivalently: g(n) ≥ (1/c)·f(n)
Let c' = 1/c > 0. Then: g(n) ≥ c'·f(n) for all n ≥ n₀.
By definition of Omega: g(n) = Ω(f(n)). ✓
Part 2: g(n) = Ω(f(n)) ⟹ f(n) = O(g(n))
Assume g(n) = Ω(f(n)).
By definition of Omega: ∃ constants c > 0 and n₀ ≥ 0 such that 0 ≤ c·f(n) ≤ g(n) for all n ≥ n₀.

Page 18 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Dividing both sides by c (since c > 0):

f(n) ≤ (1/c)·g(n)
Let c' = 1/c > 0. Then: f(n) ≤ c'·g(n) for all n ≥ n₀.
By definition of Big-O: f(n) = O(g(n)). ✓
Conclusion: f(n) = O(g(n)) ⟺ g(n) = Ω(f(n)) ■ QED

8.3 Proof: f(n) = 5n² + 6n + 4 is O(n²)

Required: Prove that 5n² + 6n + 4 = O(n²)
By definition of Big-O, we need to find constants c > 0 and n₀ ≥ 0 such that:
0 ≤ f(n) ≤ c·n² for all n ≥ n₀
Proof:
Start with f(n) = 5n² + 6n + 4
For n ≥ 1: we know that n ≤ n² and 1 ≤ n²
Therefore:
5n² + 6n + 4 ≤ 5n² + 6n² + 4n² [since n ≤ n² and 1 ≤ n² for n ≥ 1]
= 5n² + 6n² + 4n²
= 15n²
So: f(n) = 5n² + 6n + 4 ≤ 15n² for all n ≥ 1.
Choosing c = 15 and n₀ = 1:
0 ≤ 5n² + 6n + 4 ≤ 15·n² for all n ≥ 1
∴ f(n) = 5n² + 6n + 4 = O(n²) ■ QED
Verification with n = 2: f(2) = 5(4) + 6(2) + 4 = 20 + 12 + 4 = 36. c·n² = 15·4 = 60. 36 ≤ 60. ✓

Page 19 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

9. Algorithm: Find Largest Number with Complexity Analysis

9.1 Problem Statement
Given a list/array A of n integers, find and return the largest (maximum) number in the list.

9.2 Algorithm in Pseudocode

Algorithm FindLargest(A, n)
Input: Array A[1..n] of n integers, n is the size of the array
Output: The largest integer in A

Step 1: Set max ← A[1] // Initialize max with first element

Step 2: Set i ← 2 // Start loop from second element
Step 3: While i ≤ n do // Iterate through all elements
Step 4: If A[i] > max then // Compare current element with max
Step 5: max ← A[i] // Update max if larger found
Step 6: End If
Step 7: i ← i + 1 // Move to next element
Step 8: End While
Step 9: Return max // Return the largest value

9.3 Step-by-Step Trace Example

Input: A = [3, 7, 1, 9, 4, 6], n = 6
Step i A[i] max (before) A[i] > max? max (after)
Init — — — 3 (A[1])
i=2 7 3 Yes 7
i=3 1 7 No 7
i=4 9 7 Yes 9
i=5 4 9 No 9
i=6 6 9 No 9
Return — — — 9 (Result)

9.4 Time Complexity Analysis

Step Count Table
Line Code Cost Times Executed
1 max ← A[1] c₁ 1
2 i←2 c₂ 1
3 While i ≤ n (condition c₃ n times (n-1 loop + 1 final check)
check)

Page 20 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

4 If A[i] > max c₄ n-1 times

5 max ← A[i] (only if c₅ At most n-1 times
condition true)
7 i←i+1 c₆ n-1 times
9 Return max c₇ 1

Total operations T(n) = c₁ + c₂ + c₃·n + c₄·(n-1) + c₅·(n-1) + c₆·(n-1) + c₇

T(n) = (c₃ + c₄ + c₅ + c₆)·n + (c₁ + c₂ + c₇ - c₄ - c₅ - c₆)
T(n) = a·n + b where a and b are constants
Time Complexity = O(n)
• Best Case: O(n) — even in the best case (sorted descending), we must check all n
elements
• Worst Case: O(n) — same as above
• Average Case: O(n) — always requires a complete pass through all n elements
All three cases are O(n) because we must examine every element at least once to guarantee
finding the maximum.

9.5 Space Complexity Analysis

Variable / Component Space Required Notes
Input Array A[1..n] O(n) n integers stored in input
Variable: max O(1) Single integer variable
Variable: i (loop counter) O(1) Single integer variable
Variable: n (size) O(1) Single integer constant
Return value O(1) Single integer result
Total Auxiliary Space O(1) Only constant extra space used

Auxiliary Space Complexity = O(1)

Total Space Complexity = O(n) + O(1) = O(n)
The algorithm is highly space-efficient — it uses only a constant amount of extra memory
regardless of input size, making it an in-place algorithm.

Page 21 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

10. Detailed Distinction: Big-O, Omega, and Theta Notations

The three most important asymptotic notations provide different types of bounds on algorithm
complexity. Understanding their distinctions is essential for rigorous algorithm analysis.

10.1 Big-O Notation — O(f(n))

Big-O provides an asymptotic upper bound. It answers: 'What is the slowest this algorithm can run?'
Formal Definition: f(n) = O(g(n)) iff ∃ c > 0, n₀ ≥ 0: 0 ≤ f(n) ≤ c·g(n) ∀ n ≥ n₀
Visual interpretation: On a graph, c·g(n) lies ABOVE f(n) for all n ≥ n₀.
• Example 1: f(n) = 3n + 5 = O(n) — choose c = 4, n₀ = 5: 3n+5 ≤ 4n for n ≥ 5
• Example 2: f(n) = n² = O(n³) — a function can have many valid Big-O bounds; O(n²) is the
tightest
• Example 3: f(n) = 2n² + 3n = O(n²) — choose c = 3, n₀ = 3: 2n²+3n ≤ 3n² for n ≥ 3
Key Property: Big-O is the most widely used notation in practice because it guarantees the worst
case. When we say an algorithm is O(n log n), we guarantee it won't do worse than n log n
regardless of input.

10.2 Omega Notation — Ω(f(n))

Omega provides an asymptotic lower bound. It answers: 'What is the fastest this algorithm can
possibly run?'
Formal Definition: f(n) = Ω(g(n)) iff ∃ c > 0, n₀ ≥ 0: 0 ≤ c·g(n) ≤ f(n) ∀ n ≥ n₀
Visual interpretation: c·g(n) lies BELOW f(n) for all n ≥ n₀.
• Example 1: f(n) = 3n + 5 = Ω(n) — choose c = 1, n₀ = 1: n ≤ 3n+5 for all n ≥ 1
• Example 2: f(n) = n² = Ω(n) — valid lower bound, but not the tightest
• Example 3: f(n) = 5n² + 2n = Ω(n²) — choose c = 5, n₀ = 1: 5n² ≤ 5n²+2n for n ≥ 1
Key Property: Omega is used to prove lower bound results. For example, any sorting algorithm that
uses comparisons must take at least Ω(n log n) time — no comparison-based sorter can do better
asymptotically.

10.3 Theta Notation — Θ(f(n))

Theta provides a tight (exact) bound. It answers: 'What is the exact growth rate of this algorithm?'
Formal Definition: f(n) = Θ(g(n)) iff ∃ c₁, c₂ > 0, n₀ ≥ 0: c₁·g(n) ≤ f(n) ≤ c₂·g(n) ∀ n ≥ n₀
Equivalently: f(n) = Θ(g(n)) iff f(n) = O(g(n)) AND f(n) = Ω(g(n))
• Example 1: f(n) = 3n + 5 = Θ(n) — upper bound: 3n+5 ≤ 4n (c₂=4, n₀=5); lower bound: 3n+5
≥ n (c₁=1)
• Example 2: f(n) = 5n² + 6n + 4 = Θ(n²) — upper: ≤ 15n², lower: ≥ 5n²
• Example 3: f(n) = n(n+1)/2 = Θ(n²) — the sum of first n integers grows exactly as n²
Key Property: Theta is the most informative notation. When an algorithm is Θ(n log n), its runtime is
bounded both above AND below by n log n. If we can prove both O and Omega for the same
bound, we have Theta.
Aspect Big-O O(g(n)) Omega Ω(g(n)) Theta Θ(g(n))

Page 22 of 23
Data Structures & Algorithm Analysis
Comprehensive Study Guide

Bound Type Upper bound Lower bound Tight (both bounds)

Case Focus Worst case guarantee Best case guarantee Exact/average growth rate
Condition f(n) ≤ c·g(n) f(n) ≥ c·g(n) c₁·g(n) ≤ f(n) ≤ c₂·g(n)
Is Unique? Not unique (many valid Not unique (many valid Unique (most precise)
upper bounds) lower bounds)
Most Useful For Guaranteeing max Proving algorithm lower Exact performance
resource usage bounds characterization
Interpretation At most c·g(n) At least c·g(n) Between c₁·g(n) and
operations operations c₂·g(n)
Example: f(n) = O(n²), O(n³), O(2ⁿ) — Ω(n), Ω(log n) — all Θ(n²) — only one tight
n²+n all valid valid bound

10.4 Hierarchy of Common Complexity Classes

From most efficient (best) to least efficient (worst):
O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
This hierarchy means: if algorithm A is O(n) and algorithm B is O(n²), then A is fundamentally more
scalable than B for large inputs, regardless of constants.

— End of Document —

Page 23 of 23