Algorithms and Data Structures
Published: 2025-03-24
Intro
Algorithms and Data Structures are key topics to understand in Computer Science. This post is and entry-point to my notes on Algorithms and Data Structures. Where appropriate, I will link to other articles I have written that expand deeper into particular topics.
Definitions
Algorithm
An algorithm is a sequence of instructions that solves a problem. Given an input (problem), the algorithm computes the output (solution).
Data Structure
Algorithm Categories
Measuring Algorithms
Algorithms can be measured in 3 categories
- Correctness - Computes the correct result for all inputs.
- Time Efficiency - As the input size grows, how does this affect the computation time.
- Space Efficiency - How much memory does the computation require.
An algorithms effectiveness is a balance between these measurements and the problems constraints (input size, runtime requirements, computing hardware and software).
Runtime
Runtime will typically increase as the input size grows.
When measuring an algorithm, effectiveness is based on the worst case and NOT the average case.
Big-O Notation
Big-O Notation is a method to describe the upper-bounds (worst case) scenario of a computing function as the input approaches infinity (∞).
Constant Time
Basic operatations are calclated as Constant Time O(1)
Basic operations include the following:
- Math - +, -, *, max, sin, abs, etc..
- Comparison - >=, <=, etc..
- Function Calls
- Variable Assignment/Increment/Decrement
- Memory Allocation
These operations take different amounts of time, however, for the purpose of algorithm analysis, basic operations are calculated to take 1 operation
The following function is constant time O(1) function. It will always perform 2 operations no matter the input size (list).
- Operation 1 - Get index 0 from list
- Operation 2 - Return the value
int get_first(const std::vector<int>& list) {
return list[0];
}