loop – Zaf's sharings

More loops – Hard one :)

What is the time complexity

        int j = 0;
        for(int i = 0; i < n; ++i) {
            while(j < n && arr[i] < arr[j]) {
                j++;
            }
        }

O(n)
O(n^2)
O(nlogn)
O(n(logn)^2)
Can’t say. Depends on the value of arr.

Answer: O(n)

Function comparison

These are the multiple choice questions. Please, try to understand why the answer is what it is. If you are stuck, ask in the comments.

Which of the following are not O(n²). Answer: n³/sqrt(n)
1. (15¹⁰) * n + 12099
2. n^1.98
3. n³/sqrt(n)
4. 2²⁰ * n
Sort the functions by increasing order of complexity. Answer: f3, f2, f4, f1
1. f1(n) = 2ⁿ
2. f2(n) = n^3/2
3. f3(n) = n log n
4. f4(n) = n^{log n}
Which of the following loops is the fastest? Assume the same code inside the loops. Also assume n is a positive integer. Answer: for (idx = 1; idx < n; idx *= 2)
1. for (idx = 0; idx < n; ++idx)
2. for (idx = 0; idx < n; idx += 2)
3. for (idx = 1; idx < n; idx *= 2)
4. for (idx = n; idx > -1; idx /= 2)

Loop Problems – Do the Math

Identify the space and time complexity of the following chunks of code. I will post the answers later

While loop

int a = 0, i = N;
while (i > 0) {
    a += i;
    i /= 2;
}

Select here to see the answer: Time: O(log N), Space: O(1)

Nested loop

int count = 0;
for (int i = N; i > 0; i /= 2) {
    for (int j = 0; j < i; j++) {
        count += 1;
    }
}

Select here to see the answer: Time: O(N), Space: O(1)

Theta maybe?

    int i, j, k = 0;
    for (i  = n/2; i <= n; i++) {
        for (j = 2; j <= n; j = j * 2) {
            k = k + n/2;
        }
    }

Select here to see the answer: Time: Θ(n logn), Space: O(1)

GCD

    int gcd(int n, int m) {
            if (n%m ==0) return m;
            if (n < m) swap(n, m);
            while (m > 0) {
                n = n%m;
                swap(n, m);
            }
            return n;
    }

Assume n > m
Select here to see the answer: Time: Θ(log n), Space: O(1)

Loop Problems – The basics

Identify the space and time complexity of the following chunks of code. I will post the answers later

Simple loop

int a = 0, b = 0;
for (i = 0; i < N; i++) {
    a = a + rand();
}
for (j = 0; j < M; j++) {
    b = b + rand();
}

Select here to see the answer: Time: O(N+M), Space: O(1)

Nested loop

int a = 0, b = 0;
for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        a = a + j;
    }
}
for (k = 0; k < N; k++) {
    b = b + k;
}

Select here to see the answer: Time: O(N²), Space: O(1)

Another nested loop

int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
}

Select here to see the answer: Time: O(N²), Space: O(1)