What are Data structures?
We tend to study data structures and algorithms together because they
are – as you can imagine – related.
Data structures allow us to
represent, store and access data whereas algorithms allow us
to manipulate this data.
But before diving into the relationship between data structures and
algorithms, let's start with some definitions:
It defines the relationship between the data and the operations that could be performed on the data.
Abstract data type is an abstracted data structure than can be implemented in different ways.
A dictionnary is the idea that I want to assign a value to a key.
I can implement it with a "concrete" data structure like a hashmap.
Algorithm vs Function
What is difference between a function and an algorithm?
An algorithm is an abstracted series of instructions designed to fulfilled a specific goal.A function is a "concrete" series of instruction designed to fulfill a specific goal. Typically written using a programming language.
We need data structures and functions to implement an algorithm.
Algorithm Running time
To evaluate an algorithm, we typically look at the best and worst case scenario.How many operation does my alogrithm execute in the worst case?
How many operations does it execute in the best case?
We use the Big O notation to express the worst case scenario. O stands for order.
And we use Omega (Ω) to represent the best case scenario.
In case an algorithm behaves the same in the best and in the worst case, we say that this algorithm is in theta complexity.
Array indexing will always take a constant time to execute. Therefore we can say that array indexing is in theta of 1.
| Algorithm | Big O | Omega (Ω) | Theta (Θ) |
|---|---|---|---|
| Bubble Sort | O(n²) | Ω(n) | N/A |
| Merge Sort | O(n log n) | Ω(n log n) | Θ(n log n) |
| Finding Max | O(n) | Ω(n) | Θ(n) |
| Binary Search | O(log n) | Ω(1) | N/A |
| Array Indexing | O(1) | Ω(1) | Θ(1) |
| Selection Sort | O(n²) | Ω(n²) | Θ(n²) |