Data Structures Flashcards
1
Q
Time Complexity
A
Amount of time it takes to run an algorithm
2
Q
Space Complexity
A
Amount of memory taken up by a program to run
3
Q
Asymptotic Analysis
A
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
4
Q
Big O
A
Upper bound of the algoirthm (worst case)
5
Q
Omega
A
Lower bound of the Algorithm
Best case
6
Q
Theta
A
Average case
7
Q
Rules of Big O
- Execution time of statements
A
- Return statement takes 1 unit of time
- Assignment operation/arithmetical operation all take 1 unit of time
- Drop lower order terms/constants
8
Q
O(1)
A
Constant Time
- Simple instructions
9
Q
O(n)
A
Linear Time
- if input is based on n
10
Q
O(n^2)
A
Polynomial Time
- When an algorithm is n*n = n^2
