Quiz: Time Complexity
No talking here, only testing.
int Sum1ToN(int n) {
int ans = n*(n+1)/2;
return ans;
}int getSum(int n, int m) {
int ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
ans++;
return ans;
}int doRandomStuff(int n, int m) {
int ans = 0;
for(int i = 1; i <= n; ++i) {
int var = n;
while(var > 0) {
// do some O(1) operation.
var /= 2;
}
}
for(int j = 1; j <= m; ++j)
ans++;
return ans;
}int RaceToN(int N) { // N > 1
int start = 1, steps = 0;
while(start < N) {
start *= start;
steps++;
}
return steps;
}int RaceToNAgain(int N) { // N > 1
int st = 2, steps = 0;
while(st < N) {
st *= st;
steps++;
}
return steps;
}Detailed Explanation (Spoiler Alert)
See, what we're doing is replacing st with st2 in each iteration. So, it goes like 2 -> 22 -> 24 -> 28 -> 216 and so on..
Notice that the power doubles every time (i.e. 2, then 4, then 8, then 16, and so on)
What do you think 2's power will be as soon as the while loop stops? Well, it will be approximately log2N because 2log2N = N.
Now, the power of 2 starts from 1 (i.e. st = 21) and goes all the way to log2N (i.e. st = 2log2N), and it doubles in each iteration. Now, if something is doubling in every iteration and going from 1 to X, then the number of times the loop runs is Log2X.
int trickyCode(int n) {
for(int i = 1; i <= n; i *= 2) {
for(int j = 1; j <= n; j += i) {
// do some O(1) operation
}
}
return 0;
}Detailed Explanation (Spoiler Alert)
- I believe that the outer loop is straightforward, simply running Log2N times where i goes like 1, 2, 4, 8, 16 .. so on to .. N
- About the inner loop, j travels from 1 to N, of course, but the jump it takes after each iteration is i, not 1.
- So, that means, that for a given value of i, the number of iterations of the inner loop will be N/i.
- Now, the question is, how many times will the inner loop iterate in total? the answer to this question is the resultant time complexity.
- Okay, so i goes on like 1, 2, 4, ... so on .., N. Right?
-
That means:
-
When i=1, the inner loop runs N times.
-
When i=2, the inner loop runs N/2 times.
-
When i=4, the inner loop runs N/4 times.
-
.. so on ..
- In totality, the running time will be \(N + \frac{N}{2} + \frac{N}{4} .. 1\)
- In other words, operations = N*[\(\underbrace{\mathit{1} + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ...}_{Log_2N terms}\)]
- Applying the formula for GP, we'll get operations = \(N*[\frac{1 - \frac{1}{2}^{log_2n}}{\frac{1}{2}}]\)
- After solving, operations = 2*(N - 1)
- Therefore, Time Complexity = O(N)
This is a topic you'll practice everytime you'll solve a DSA problem, doesn't matter if it's a graph problem or an array problem, time complexity is an important part everywhere.