Data Structures Flashcards
Time Complexity
Amount of time it takes to run an algorithm
Space Complexity
Amount of memory taken up by a program to run
Asymptotic Analysis
Evaluating performance of an algorithm in terms of input size and its increase
- We don’t actually see how fast it can run but rather how it increases with different inputs
Big O
Upper bound of the algoirthm (worst case)
Omega
Lower bound of the Algorithm
Best case
Theta
Average case
Rules of Big O
- Execution time of statements
- Return statement takes 1 unit of time
- Assignment operation/arithmetical operation all take 1 unit of time
- Drop lower order terms/constants
O(1)
Constant Time
- Simple instructions
O(n)
Linear Time
- if input is based on n
O(n^2)
Polynomial Time
- When an algorithm is n*n = n^2
Why use a linked list?
- For fast insertion, deletion, espeically in the middle
When use a hashmap?
When you want key-value pairs
- Fast lookups by key
- Caching or memoization
- Counting occurrences of elements
When use a HashSet?
Ensuring uniqueness
- fast checking
- removing dups
- set operations like union/intersection
When use a regular set?
When you want flexibility, can switch between hashset and treeset
- When defining APIs
When to use regular arrays?
Fixed size, better performance than primitive types
- multi-dimensional
When to use Arraylists?
When you don’t know the size
- when yolu need fasat random access
When you frequently add/remove elements at the end
How to create a new set?
Set<String> bookCategories = new HashSet<>();</String>
How to create a new LinkedList?
LinkedList<String> issuedBooks = new LinkedList<>();</String>
How to create a new ArrayList?
ArrayList<String> availableBooks = new ArrayList<>();</String>
How to create a new hashmap?
HashMap<String, Boolean> bookAvailability = new HashMap<>();
How to create a new HashSet?
HashSet<String> borrowers = new HashSet<>();</String>
