Problem 1
The answers to the other questions are as follows:
for(int i = 0; i < n; i++) for(int j = 0; j < min(i, 10); j++) cout << i*j << endl;In the above code the function call min(i, 10) returns the smaller of i and 10.
For each value of i, i = 1, 2, ..., 9, 10, the inner loop iterates i times. For each values of i > 10, the inner loop iterates 10 times. Thus the total number of times the cout statement is executed is:
1 + 2 + ... + 9 + 10 + 10 + 10 +... + 10 <= 10 + 10 + 10 +... + 10 = 10(n-1) = O(n)
For each value of i, i = 0, 1, 2, ..., 9, 10, the inner loop iterates 10 times. For each values of i > 10, the inner loop iterates i times. Thus the total number of times the cout statement is executed is:
10 + 10 + 10 +... + 10 + 11 + 12 + ... + (n-1) = 10n + (1 + 2 +... + n-11) < 10n + (1 + 2 + ... n) = 10n + n(n+1)/2 = O(n^2)
for(int i = 1; i < n; i++) for(int j = 0; j < n; j = j + i) cout << i*j << endl;The sum 1 + 1/2 + 1/3 + ... + 1/n is called the harmonic series and it is well known that this is O(log n). Use this fact in your analysis.
For each value of i, the inner loop iterates at most (n-1)/i times. Therefore the total number of times the cout statement is executed is:
(n-1) + (n-1)/2 + .... + (n-1)/(n-1) = (n-1) (1 + 1/2 + 1/3 +...+1/(n-1)) = O(n log n).