Overview:
Problem 1
#include <iostream>
using namespace std;
int arraySum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
return sum;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = arraySum(arr, n);
cout << "Sum of elements: " << sum << endl;
return 0;
}
Explanation:
The Time complexity of this code is O(n) because it performs single pass through the array of size ‘n’, where n is the number of elements in the array.
The Space complexity of this code is O(1) because it only used a constant amount of extra space (the ‘sum’ variable).
Problem 2
int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
Explanation:
The first loop is O(N) and the second loop is O(M). but since both N and M are independent variables, so we can not say which on is the leading term. Therefore Time Complexity of the given problem will be O(N+M).
Since variables size does not depend on the size of the input, therefore Space Complexity will be constant or O(1).
Problem 3
int a = 0;
for (i = 0; i < N; i++) {
for (j = N; j > i; j--) {
a = a + i + j;
}
}
Explanation:
The outer loop runs from i = 0
to i < N
. This loop will run N
times.
The inner loop runs from j = N
to j > i
. For each value of i
, the inner loop will run N - i
times.
Now, lets calculate the total number of iterations.
- When
i = 0
, the inner loop runsN
times. - When
i = 1
, the inner loop runsN - 1
times. - When
i = 2
, the inner loop runsN - 2
times. - …
- When
i = N-1
, the inner loop runs1
time.
So, the total number of iterations can be calculated as follows:
Total iterations = (N) + (N - 1) + (N - 2) + ... + 1
This is an arithmetic series sum, and you can calculate it using the formula for the sum of the first n
natural numbers, which is (n * (n + 1))/2
.
In this case, n = N
, so the total number of iterations is:
(N * (N + 1)) / 2
Problem 3
int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n / 2;
}
}
Answer = O(n log n)
Explanation:
The outer loop runs from i = n / 2
to i ≤ n
. It iterates n - (n/2) + 1
times, which simplifies to n / 2 + 1
times. In terms of complexity analysis, we consider it as O(n).
The inner loop runs from j = 2
to j ≤ n
with a doubling step size j = j * 2
. It effectively runs for log2(n)
iterations because j
is doubled each iteration until it reaches or exceeds n
.
Now, lets calculate the total number of iterations:
- The outer loop runs
n
times O(n). - The inner loop runs
log2(n)
times O(log n).
To find the overall time complexity, we multiply the complexities of the nested loops. In this case its O(n) * O(log n), which simplifies to O(n log n).
Problem 4
int a = 0, i = N;
while (i > 0) {
a += i;
i /= 2;
}
Answer =O(log N)
.
Explanation:
In this code, we have a while loop that repeatedly divides i
by 2 until i
becomes less than or equal to 0.
- The loop starts with
i = N
. - In each iteration, it adds the current value of
i
toa
. - Then, it divides
i
by 2.
Lets analyze the number of iterations:
- In the first iteration,
i = N
. - In the second iteration,
i = N / 2
. - In the third iteration,
i = (N / 2) / = N / 4
. - This pattern continues until
i
becomes less than or equal to 0, which happens wheni = 0
.
To find the total number of iterations, we need to count how many times we can divide i
by 2 until it becomes 0. This is essentially a logarithmic operation base 2.
So, the time complexity of the above problem is O(log N).