A collection of algorithms and data structure implementations developed during my Computer Engineering degree at UNISAL (Centro Universitário Salesiano de São Paulo).
The repository explores fundamental computer science concepts through practical implementations in Python and C, including graphs, the Karatsuba multiplication algorithm, linked lists, stacks, and dynamically allocated stacks.
The goal of this project is to strengthen my understanding of data structures, algorithm design, memory management, and computational complexity.
- About the Project
- What Is Algorithm Complexity?
- How to Analyze Algorithm Complexity
- Big O Notation
- Data Structures and Algorithms
- Languages and Technologies
- Learning Objectives
- Author
- License
This repository contains educational implementations created while studying programming, data structures, and algorithm analysis at UNISAL.
Each implementation provides an opportunity to explore how an algorithm works, how data is organized in memory, and how different design choices affect performance.
The repository includes implementations in Python and C, allowing comparisons between a high-level language with built-in data structures and a lower-level language that requires explicit memory management.
Algorithm complexity describes how the resources required by an algorithm change as the input size increases.
The two main resources analyzed are:
- Time complexity: how the execution time or number of operations grows with the input size.
- Space complexity: how the memory requirements grow with the input size.
Complexity analysis helps us evaluate algorithm efficiency and understand how an implementation may behave when processing larger inputs.
For example, an algorithm that processes every element in a list generally has linear time complexity, while an algorithm that compares every element with every other element may have quadratic time complexity.
To analyze an algorithm, identify the input size and determine how the number of relevant operations grows as that input increases.
Consider these examples:
Linear complexity — O(n)
def print_items(items):
for item in items:
print(item)The loop processes each element once. If the list contains twice as many elements, the number of loop iterations also doubles.
Quadratic complexity — O(n²)
def print_pairs(items):
for first in items:
for second in items:
print(first, second)The nested loops process every ordered pair of elements. If the input size doubles, the number of pairs grows approximately fourfold.
When analyzing an algorithm, focus on the dominant term and ignore constant factors in asymptotic notation.
For example:
- O(3n) simplifies to O(n).
- O(n² + n) simplifies to O(n²).
- O(n + log n) simplifies to O(n).
These simplifications describe asymptotic growth rather than exact execution time.
Big O notation describes an asymptotic upper bound on an algorithm's growth rate. It is commonly used to discuss worst-case time complexity, although it can also describe other bounds when appropriately defined.
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing an array element by index |
| O(log n) | Logarithmic | Binary search in a sorted array |
| O(n) | Linear | Traversing a list |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Comparing all pairs of elements |
| O(2ⁿ) | Exponential | Certain brute-force subset algorithms |
An algorithm with a lower asymptotic growth rate often scales better for large inputs. However, actual performance also depends on implementation details, input characteristics, memory usage, and constant factors.
A graph is a data structure consisting of vertices (nodes) and edges connecting them. Graphs can represent networks, relationships, routes, and many other real-world systems.
- Python: graph representations using dictionaries or adjacency lists.
- C: graph representations using structures, pointers, and adjacency lists.
Let V represent the number of vertices and E the number of edges.
| Operation | Typical Complexity |
|---|---|
| Add a vertex | O(1) amortized with a suitable representation |
| Add an edge | O(1) amortized for an adjacency-list insertion |
| Breadth-First Search (BFS) | O(V + E) |
| Depth-First Search (DFS) | O(V + E) |
These complexities depend on the graph representation and implementation. For example, checking whether an edge exists can take O(degree(v)) with an adjacency list, or O(1) with an adjacency matrix.
Shortest-path complexity also depends on the algorithm. Dijkstra's algorithm, for example, can run in O((V + E) log V) with a suitable adjacency-list representation and priority queue.
Karatsuba is a divide-and-conquer algorithm for multiplying large integers. It reduces the number of recursive multiplications required compared with the traditional multiplication approach.
Suppose two numbers are divided into high and low parts:
- x = a × 10ᵐ + b
- y = c × 10ᵐ + d
Instead of calculating four products, Karatsuba calculates three:
- z₂ = a × c
- z₀ = b × d
- z₁ = (a + b)(c + d) − z₂ − z₀
The final result is:
xy = z₂ × 10²ᵐ + z₁ × 10ᵐ + z₀
This method reduces the number of recursive multiplications from four to three.
The recurrence is:
T(n) = 3T(n/2) + O(n)
Using the Master Theorem, the asymptotic time complexity is:
O(n^log₂3) ≈ O(n^1.585)
Here, n represents the number of digits or the input size in an appropriate representation.
The implementation may use recursion and helper functions for operations such as addition and subtraction. When numbers are represented as strings, these operations can be implemented without relying on fixed-width integer types.
A linked list is a linear data structure made up of nodes. Each node stores a value and a reference or pointer to another node.
Unlike a conventional array, linked-list elements do not need to occupy contiguous memory locations.
| Operation | Typical Complexity |
|---|---|
| Insert at the beginning | O(1) |
| Remove from the beginning | O(1) |
| Search for an element | O(n) |
| Access an element by position | O(n) |
In C, linked lists provide practical experience with pointers, dynamic memory allocation, and memory deallocation. In Python, references between objects make the implementation simpler, although the underlying structure still requires traversal to access elements by position.
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element inserted is the first element removed.
The main operations are:
push: add an element to the top.pop: remove and return the top element.peek: inspect the top element without removing it.is_empty: check whether the stack contains any elements.
| Operation | Typical Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| Check whether empty | O(1) |
These complexities assume an implementation with constant-time access to the top. Python lists provide amortized O(1) append and pop operations at the end. A fixed-size array implementation in C also supports O(1) stack operations while capacity remains available.
A dynamic stack can grow or shrink during execution instead of relying on a fixed-size array.
In this repository, the term can refer to a stack implemented using a linked list, where each insertion allocates a new node and each removal releases a node.
- The stack can grow as needed, subject to available memory.
- No fixed array capacity is required.
- Insertion and removal at the top take O(1) time.
- Each linked-list node requires additional memory for a pointer.
- Dynamic allocation and deallocation must be handled carefully in C.
- Allocation failures and attempts to remove an element from an empty stack should be handled explicitly.
The exact behavior depends on the implementation used in each source file.
- Python — algorithm implementations and data structures.
- C — pointers, structures, linked lists, and dynamic memory allocation.
- Git and GitHub — version control and project documentation.
This project supports the study of:
- Fundamental data structures and algorithms.
- Time and space complexity analysis.
- Divide-and-conquer techniques.
- Graph representations and traversal concepts.
- Linked lists and stack operations.
- Memory allocation and deallocation in C.
- Differences between Python and C implementations.
Lucas Neves da Silva
Computer Engineering student at UNISAL.
This repository reflects my academic learning process and my continued practice in programming, algorithms, and data structures.
This project is distributed under the MIT License. See the LICENSE file for details.