Quiz on Complexity Analysis of Algorithms

What is the time complexity of the following function?

int fun(int n) {

int count = 0;

for (int i = n; i > 0; i /= 2)

for (int j = 0; j < i; j++)

count += 1;

return count;

}

• O(n*log(n*log(n)))

• O(n^2)

• O(n)

• O(n*log(n))

What is the time complexity of the following function?

int fun(int n) {

int count = 0;

for (int i = 0; i < n; i++)

for (int j = i; j > 0; j--)

count = count + 1;

return count;

}

• Theta(n^2)

• Theta(n*(log(n*log(n))))

• Theta(n)

• Theta(n*log(n))

O(n^2) is the worst-case time complexity, so among the given options it can represent:

• All of the above

• O(n log n)

• O(1)

• O(n)

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3, and f4?

f1(n) = 2n

f2(n) = n^(3/2)

f3(n) = n*log(n)

f4(n) = n log(n)

• f2, f3, f4, f1

• f3, f2, f4, f1

• f3, f2, f1, f4

• f2, f3, f1, f4

What is the time complexity of the following function?

void fun(int n, int arr[]) {

int i = 0, j = 0;

for (; i < n; ++i)

while (j < n && arr[i] < arr[j])

j++;

}

• O(n^2)

• O(n)

• O(n*log(n^2))

• O(n*log(n))

In a competition, four different functions are observed. If n is the size of input (positive), which function is most efficient? If n is the size of input(positive), which function is most efficient(if the task to be performed is not an issue)?

• for(i = 0; i < n; i++)

• for(i = 0; i < n; i += 2)

• for(i = 1; i < n; i *= 2)

• for(i = n; i <= n; i /= 2)

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

• X will be a better choice for all inputs except possibly large inputs

• X will be a better choice for all inputs except possibly small inputs

• X will be a better choice for all inputs

• Y will be a better choice for small inputs

In the following C function, let n >= m. How many recursive calls are made by this function?

int gcd(n, m) {

if (n % m == 0)

return m;

n = n % m;

return gcd(m, n);

}

• Θ(sqrt(n))

• Θ(log(log(n)))

• Ω(n)

• Θ(log(n))