Big O is a way to categorise an algorithms time or memory requirements based on input
Big O is used to help make decisions on the type of data structures and algorithms you’d use
The easiest way to measure the complexity of algorithms is the upper bound
Example 1
public static String bigExample(String n) {
int sum = 0;
for (int i = 0; i < n.length(); i++) {
sum += n.charAt(i);
}
return String.valueof(sum);
}
trick for time complexity: Look for loops
one loop for the example above so O(n)
Example 2
public static String bigExample(String n) {
int sum = 0;
for (int i = 0; i < n.length(); i++) {
sum += n.charAt(i);
}
for (int i = 0; i < n.length(); i++ {
sum += n.charAt(i);
}
return String.valueof(sum);
}
O(2n) → O(n) why: Big O is meant to describe the upper bound of the algorithm so the constant eventually becomes irrelevant. basically, the relative growth of different complexity classes (like N vs N²) becomes more significant than small constant multipliers
Common complexities
Important concepts to note: 1.growth is with respect to the input
2.constants are dropped