Fellow Coder 
When determining the time complexity of an algorithm, we follow certain rules. For instance:
1. Ignoring Constant Terms
If the complexity of an algorithm is written as O(3n+2), it can be simplified to O(n). This is because in the context of Asymptotic Notation, we focus on the relationship—whether it is linear, logarithmic, etc.—rather than the exact number of operations.
For very large values of n, constant terms have minimal impact. For example:
- If n = 1, then O(3n+2)=(3×1+2)=5O(3n + 2) = (3 \times 1 + 2) = 5.
- If n = 1,000,000, adding 2 makes no significant difference for a computer.
The same applies to coefficients. When n = 10, 3n=30, and when n=20 3n = 60. However, if the term were n2n^2, the result would be significantly larger. For n=10n = 10, n2=100n^2 = 100, and for n=20n = 20, n2=400n^2 = 400. Hence, constants are ignored in time complexity.
2. Dropping Non-Dominant Terms
If the complexity is O(n2+n+4)O(n^2 + n + 4), after removing the constant, it becomes O(n2+n)O(n^2 + n).
Here, the dominant term is n2n^2. For large nn, n2n^2 grows much faster than nn.
For instance:
- If n=10n = 10, n2+n=100+10=110n^2 + n = 100 + 10 = 110.
- If n=100n = 100, n2+n=10,000+100=10,100n^2 + n = 10,000 + 100 = 10,100.
The effect of nn becomes negligible as nn grows larger, so we simplify the complexity to O(n2)O(n^2).
3. Multiple Loops
Consider the following code snippets:
Example 1 (Separate Loops):
test_case = int(input())
for i in range(test_case):
print(f'this will print {i} in first loop')
for j in range(test_case):
print(f'this will print {j} in second loop')
Here, the first loop runs O(test_case)O(test\_case) times, and the second loop also runs O(test_case)O(test\_case). The total complexity is O(test_case+test_case)=O(test_case)O(test\_case + test\_case) = O(test\_case) because the loops are sequential.
Example 2 (Nested Loops):
test_case = int(input())
for i in range(test_case):
print(f'this will print {i} in first loop')
for j in range(test_case):
print(f'this will print {j} in second loop')
In this case, for every iteration of the outer loop, the inner loop runs completely. Thus, the complexity is O(test_case×test_case)=O(test_case2)O(test\_case \times test\_case) = O(test\_case^2).
4. Logarithmic Complexity
Let’s first understand what a logarithm is. Recently, I watched a lecture by Eddie Woo, which explained this concept well.
A logarithm is another way to view exponential growth. For instance:
- Exponential: BaseExponent\text{Base}^{\text{Exponent}}
- Example: 24=162^4 = 16, where base = 2 and exponent = 4.
Imagine you have a magic stick that doubles in size every second:
- At t=0t = 0, size = 11 meter (202^0).
- At t=1t = 1, size = 22 meters (212^1).
- At t=2t = 2, size = 44 meters (222^2).
- At t=3t = 3, size = 88 meters (232^3).
Now, if you know the final size and the growth rate but not the time, you can calculate the time by repeatedly dividing the final result by the growth rate until the result is 11.
This relationship is represented as:
Growth RateTime=Result\text{Growth Rate}^{\text{Time}} = \text{Result}
LogGrowth Rate(Result)=Time\text{Log}_{\text{Growth Rate}}(\text{Result}) = \text{Time}
For algorithms where the input size reduces by a fixed rate in every step (e.g., Binary Search), the complexity is O(logN)O(\log N).
5. Recursive Functions
Consider this function:
def recursive(n):
if n <= 1:
return 1
return recursive(n - 1) + recursive(n - 1)
print(recursive(5))
Here, each function call branches into two, and the depth of the recursion is determined by nn.
For n=5n = 5:
- At the first level, there is 1 call.
- At the second level, there are 2 calls.
- At the third level, there are 22=42^2 = 4 calls.
This forms a binary tree with 2n2^n calls at the deepest level. Hence, the time complexity is O(2n)O(2^n), which is exponential.
Thank you for reading! If you notice any mistakes, please let me know. We may create a video on this topic soon—stay tuned by subscribing to our YouTube channel.
