This is a homework problem I have. I could not find whether it was against the rules or not to post such a question. I cannot figure this one out. I would appreciate help in understanding why the answer is what it is.
I can say with confidence that in this case, we would be concerned with θ as being the most precise description of the asymptotic complexity since the loops never terminate early.
I understand that the outer for loop will always run n times, and that the inner for loop will run less times as i increases.
The answer would then be θ(n * running time of inner loop).
I think that either ∑ from k=1 to n of n(n+1)/2 or the harmonic series ∑ from k = i to N of i/1 could be useful here, but I don't know how to apply either. We went over relatively simple examples in class and I understand those, but not this one.
void function(int n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j += i) {
std::cout << "*";
}
}
}
Making a table with theoretical values for i and j when n is a certain value and trying to find a mathematical relationship between i and j.
Ex: say n = 3.
| i | j |
|---|---|
| 1 | 1 |
| 1 | 2 |
| 1 | 3 |
| 2 | 1 |
| 2 | 3 |
| 3 | 1 |
Your total complexity is
(n / 1) + (n / 2) + ... + (n / n) =
n * ((1 / 1) + (1 / 2) + ... (1 / n)) =
n * (ln(n) + 0.577) which is roughly nlogn.
The reason is that
(1 / 1) + (1 / 2) + ... + (1 / n)
is known as the harmonic series, see https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Partial_sums)