Big-O-Smallest-to-Largest Flashcards
1: Constant
O(1)
2: Logarithimic
O(log n)
3: Linear
O(n)
4: Linearithmic
O(n*log n)
5: Quadratic
O(n^2)
6: Cubic
O(n^3)
8: Exponential
O(2^n) or O(e^n), where e > 1
9: Factorial
O(n!)
- Quartic
O(n^4)
Array/List gets iterated over c * length times. Define Big O
O(n), where is n is the length of array or list
How will you identify O(log n)
When number of elements in the problem space gets halved each time.
How will you identify O(N^2)/Ouadratic
When we have a single nested loop
for (int i=0; i< n; i++{
for (int j=0; i
Find Big O for this
for (int i=0; i
O(nm)
Find Big O for this
for (int i=0; i
O(n^2)
Find Big O for this
for (int i=0; i
O(n)
Outer loop i is doubled and incremented each time.
Find Big O for this
i = //constant
n = //constant
k = //constant
while (i < n){
i*=k;
// Statement(s) that take(s) constant time
}
O(log to base K of n)
if K is 2, then O(log n)
Because the loop count is being doubled every time.
Find Big O for this
p = 0
for (i = 0; p < n; i++) {
p = p+i;
// Statement(s) that take(s) constant time
}O(sqrt(n))
For loop will run K time, as long as p < n
When ever we see, i getting incremented by its own value, then it will run sqrt of n time.
Find Big O for this
for(i = 0; i < n; i++){
i = i*2;
// Statement(s) that take(s) constant time
}
And for this
for(i = 0; i < n; i++){
i = i+2;
// Statement(s) that take(s) constant time
}
First one: O(log n), as i is doubled every time.
Second one: O(sqrt n), as i is incremented by self every time.
Complexity for
Accessing an element in an array
O(1)
Complexity for
Traversing an array
O(N)
Complexity for
Updating an element in an array
O(1)
Complexity for
Inserting an element in the beginning
O(n)
Complexity for
Appending an element in the end
Static Array: O(n)
Dynamic Array: Amortized O(1)
Complexity for
Inserting an element in the middle
O(n)
