Practice Problems on Complexity Analysis

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 runs N times.
• When i = 1, the inner loop runs N - 1 times.
• When i = 2, the inner loop runs N - 2 times.
• …
• When i = N-1, the inner loop runs 1 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.

1. The loop starts with i = N.
2. In each iteration, it adds the current value of i to a.
3. 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 when i = 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).