Data structures introduction
Abstract Data Type
is an abstraction of a data structure which provides only the interface to which a data structure must adhere to. The interface does not give any specific details about how something should be implemented or in what programming language.
| Abstraction(ADT) | Implementation (DS) |
|---|---|
| List | Dynamic Array, Linked List |
| Queue | Linked List based Queue, Array based Queue, Stack based Queue |
| Map | Tree Map, Hash Map / Hash Table |
| Vehicle | Golf cart, Bicycle, Smart car |
Big-O Notation
gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrararily large
| Time | Complexities |
|---|---|
| Constant Time | O($1$) |
| Logarithmic Time | O($log(n)$) |
| Linear Time | O($n$) |
| Linearithmic | O($nlog(n)$) |
| Quadric Time | O($n^2$) |
| Cubic Time | O($n^3$) |
| Exponential Time | O($b^n$) |
| Factorial Time | O($n!$) |