Data Structures and Algorithms CE 373 Study Notes

Data Structures and Algorithms: CE 373

Course Introduction

Lecturer: Vincent M. Nofong, Ph.D.
Department: Computer Science and Engineering
Institution: University of Mines and Technology, Tarkwa - Ghana
Date: January 27, 2026

The course aims to introduce students to data structures and algorithms, focusing on the design of effective or "good" data structures and algorithms.

Key Definitions

• Data Structure: A systematic way of organizing and accessing data.

• Algorithm: A step-by-step unambiguous procedure for performing some task within a finite amount of time.

Importance of the Course

Data structures and algorithms are foundational to computing. To classify some of them as "good," precise methods of analysis are necessary.

Algorithm Analysis

Why Analyze Algorithms?

Several algorithms exist for the same problem; for instance, sorting can be accomplished using multiple methods, including:

1. Insertion Sort

2. Selection Sort

3. Quick Sort

Algorithm analysis aids in determining the most efficient algorithm based on time and space consumption.

Criteria for Judging Algorithms

1. Correctness: Does the algorithm provide a solution to the problem within a finite number of steps?

2. Efficiency: What are the resource requirements (in terms of memory and time) to execute the algorithm?

Goals of Algorithm Analysis

The primary goal is to compare algorithms in terms of runtime and additional factors like memory and developer effort.

What is Runtime Analysis?

Runtime analysis involves determining how processing time increases as the size of the problem size increases. The input size can vary based on the problem type, including:

• Size of an array

• Polynomial degree

• Number of elements in a matrix

• Vertices and edges in a graph

Comparing Algorithms

Experimental Analysis

Although algorithms can be compared using their runtimes experimentally, this approach has challenges:

• Hardware/Software Dependency: Runtimes can only be directly compared if tests are conducted in identical environments.

• Limited Test Inputs: Experiments can only account for a limited set of inputs resulting in potentially significant overlooked runtimes.

• Full Implementation Requirement: A complete implementation of an algorithm is needed to analyze its running time experimentally.

Advanced Analysis Techniques

To analyze efficiency without experimental analysis, we can:

• Conduct analysis based on high-level descriptions of the algorithms.

• Define a set of primitive operations (e.g., assigning values, performing arithmetic operations, comparing numbers, accessing array elements, method calls, and returns).

• Count the executed primitive operations to establish a runtime measure.

Measuring Operation Counts as a Function of Input Size

To understand algorithm runtime growth, associate a function $f(n)$ with each algorithm to characterize primitive operation counts as a function of input size $n$. This allows comparisons across three analysis types:

1. Worst Case: Identifies the input type that results in maximum execution time.

2. Best Case: Identifies input for minimum execution time.

3. Average Case: Predicted runtime based on running the algorithm multiple times with various inputs generated from a specified distribution.

Determining Which Case to Use

• Average-case analysis is complex as it requires defining the probability distribution of input sets, which is often difficult.

• Worst-case analysis is simpler as it only necessitates finding the worst-case input. This method often ensures that algorithms perform well under all input scenarios.

Asymptotic Analysis

Understanding the expressions for best, average, and worst cases involves identifying upper and lower bounds of algorithm runtime. This is expressed using functions that correlate the input size $n$ to values that determine growth rates.

Notations Used in Asymptotic Analysis

1. Big-O Notation (O): Indicates that function $f(n)$ is growth-wise less than or equal to function $g(n)$ multiplied by a constant factor, in the asymptotic sense as $n$ approaches infinity.

   • Definition: For functions $f(n)$ and $g(n)$:
     f(n) ext{ is } O(g(n)) ext{ if there exists a } c > 0 ext{ and an } n0 ext{ such that } f(n) ext{ is less than or equal to } c imes g(n) ext{ for } n ext{ greater than or equal to } n0.

Examples of Big-O Notation

1. The function $8n + 5$ is $O(n)$.

2. The function $n^4 + 100n^2 + 10n + 50$ is $O(n^4)$.

3. The function $100n^2 + 10n$ is $O(n^2)$.

Properties of Big-O Notation

• Allows the neglecting of constant factors and lower-order terms in order to focus on the main factors impacting growth rate.

  • Example: $5n^4 + 3n^3 + 2n^2 + 4n + 1$ is $O(n^4)$ as justifying $(5 + 3 + 2 + 4 + 1)n^4$ leads to a constant factor of 15, starting from $n_0 = 1$.

Additional Observations Regarding Big-O Notation

• For polynomial functions of degree $d$, where $f(n) = a<em>0 + a</em>1 n + … + a<em>d n^d$ (with ad > 0):
  $f(n) ext{ is } O(n^d)$ when $n ext{ is greater than or equal to } 1.$

Big-Omega Notation (Ω)

• Provides an asymptotic measure indicating that a function grows at a rate that is greater than or equal to another function.

  • Definition: For functions $f(n)$ and $g(n)$:
    f(n) ext{ is } Ω(g(n)) ext{ if } g(n) ext{ is } O(f(n)), ext{ implying existence of } c > 0 ext{ and } n_0 ext{ where } f(n) ext{ is greater than or equal to } c imes g(n).

Big-Omega Examples

1. For $3n ext{ log } n - 2n$, we observe it is $Ω(n ext{ log } n)$ because $3n ext{ log } n - 2n ext{ is greater than or equal to } n ext{ log } n$ for $n ext{ greater than or equal to } 2$.

2. The expression $100n^2 + 10n + 50$ is also $Ω(n^2)$.

Big-Theta Notation (Θ)

• Represents an asymptotic measure that indicates a function's growth rate matches another, up to constant factors.

  • Definition: $f(n) ext{ is } Θ(g(n)) ext{ if it is both } O(g(n)) ext{ and } Ω(g(n)), ext{ implying bounds of the form } c' g(n) ext{ and } c'' g(n) ext{ exist for all } n ext{ greater than or equal to } n_0.$

Big-Theta Examples

1. For the function $3n ext{ log } n + 4n + 5 ext{ log } n$, it is $Θ(n ext{ log } n)$ since:
   $3n ext{ log } n ext{ is less than or equal to } 3n ext{ log } n + 4n + 5 ext{ log } n ext{ is less than or equal to } (3 + 4 + 5)n ext{ log } n ext{ for } n ext{ greater than or equal to } 2.$

Functions for Comparative Analysis

• Common Growth Rate Functions in algorithm analysis include:

  1. Constant Function: $f(n) = c$

  2. Logarithm Function: $f(n) = ext{log}_b n$ for some constant b > 1

  3. Linear Function: $f(n) = n$

  4. N-Log-N Function: $f(n) = n ext{ log } n$

  5. Quadratic Function: $f(n) = n^2$

  6. Cubic Function and Other Polynomials: Cubic Functions: $f(n) = n^3$. Polynomials: $f(n) = a<em>0 + a</em>1n + a<em>2n^2 + a</em>3n^3 + … + a_d n^d$

Determining Runtime Complexity of Algorithms

Sequence of Statements

If each statement is simple, the time complexity for each is constant, leading to an overall complexity of:

• $O(1)$

If-then-Else Statements

The worst-case execution time is defined as:

• $ext{max}( ext{time(sequence 1)}, ext{time(sequence 2)})$

  • Example: For two sequences where one is $O(n)$ and the other is $O(1)$, the overall worst-case time for the if-else statement is $O(n)$.

Loops

The total time complexity of loops can be evaluated as:

• For constant loops: $O(1)$

• For linear iterations: $O(n)$

• For nested loops: $O(n^2)$

Nested Loops

The total complexity for nested loops simplifies to:

• $O(n^2)$

Consecutive Statements

For consecutive statements, total time complexity can be determined as:

• Example: $c<em>0 + c</em>1n + c_2n^2 = O(n^2)$

Other Time Complexities

• O(log n): Relevant if loop variables double or halve
  every iteration.

• O(log log n): Applies when loop variables vary exponentially.

Examples of Time Complexity

1. If a loop doubles its control variable starting at 1, the number of iterations can be categorized as:

   • If after the $k$-th iteration the variable equals $n$ (i.e., $2^k = n$), then:

   • Taking logs on both sides yields: $k = ext{log}(n)$, hence $O(log n)$.

Space Complexity of Algorithms

Definition: Space complexity quantifies the amount of memory required by an algorithm, accounting for:

• All variables (global and local)

• Dynamic data structures

• Stack contents during recursion

Constants and Linear Space Complexity

• If a constant number of variables are necessary for execution, the space complexity is:

  • $O(1)$

• If an algorithm requires declaring an array of size $n$, the complexity denotes:

  • $O(n)$

Complexity Calculations

Space complexity can be trickier than time complexity, as different variables/data structures may not be needed simultaneously. Global variables persist in memory, while local variables and stack data are only present during method execution.