================Basic primer===========

1. What is the time, space complexity of following code :

int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
Assume that rand() is O(1) time, O(1) space function.

a) O(N * M) time, O(1) space
b) O(N + M) time, O(N + M) space
c) O(N + M) time, O(1) space (Correct)
d) O(N * M) time, O(N + M) space
e) O(N * M) time, O(N * M) space

=================================

2. What is the time, space complexity of following code :

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;
}

a) O(N * N) time, O(1) space(Correct)

b)O(N) time, O(N) space

c)O(N) time, O(N) space
d)O(N * N) time, O(N) space
e)O(N * N * N) time, O(1) space

===================================

3. What is the time complexity of the following code :

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

a) O(N)
b) O(N*log(N))
c) O(N * Sqrt(N))
d) O(N*N) (Correct)

==================================

4. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

a) X will always be a better choice for all inputs
b) X will always be a better choice for large inputs
Correct !——

c) X will always be a better choice for small inputs
d) Y will always be a better choice for small inputs

===================================

5. What is the time complexity of the following code :

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

a) O(N)
b) O(Sqrt(N))
c) O(N / 2)
d) O(log N) Correct !

========================================

6. What is time complexity of following code :

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

a) O(N * N)
b) O(N * log N)
c) O(N * log(log(N)))
d) O(N)
Correct !

Asked by AMAZON

====================================

7. What is the time complexity of the following code :

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

a) Θ(n)
b) Θ(nLogn) Correct !

Θ(n^2)
Θ(n^2 / Logn)
Θ(n^2Logn)

=====================================

8. In the following C++ function, let n >= m.

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;
}
What is the time complexity of the above function assuming n > m?.
Θ symbol represents theta notation and Ω symbol represents omega notation.

a) Θ(logn) Correct !

b) Ω(n)
c) Θ(loglogn)
d) Θ(sqrt(n))