DAA Quiz 1 - Time Complexity

What is time complexity of fun()?

int fun(int n)

{

int count = 0;

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

count += 1;

return count;

}

• O(n²)

• O(Logn)

• O(n)

• O(nLognLogn)

What is the time complexity of fun()?

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)

• Theta (n²)

• Theta (nLogn)

• Theta (nLognLogn)

Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

• A(n)=Omega(W(n))

• A(n)=Theta(W(n))

• A(n)=O(W(n))

• None of these

In a competition, four different functions are observed. All the functions use a single for loop and within the for loop, same set of statements are executed. Consider the following for loops, 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 > -1; i /= 2)

What is the complexity of the function unknown()

int unknown(int n) {

int i, j, k = 0;

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

for (j = 2; j <= n; j = j * 2)

k = k + n/2;

return k;

}

• 𝞱(n²)

• 𝞱(nlogn)

• 𝞱(n²logn)

• 𝞱(n³logn)

Say True or False

(n² + 5) belongs to O(n + 20)

• True

• False

Say True or False

(n+6) belongs to BigOmega(n³)

• False

• True

void f(n)

{

ans = 0

while (n > 0)

{

ans += n % 10

n /= 10;

}

print(ans)

}

What is the time complexity of this code?

• O(log n to base 2)

• O(log n to base 3)

• O(log n to base 10)

• O(n)

void f()

{

ans = 0

for (i = n; i >= 1; i /= 2)

{

for (j = 1; j <= m; j *= 2)

{

ans += (i * j)

}

}

print(ans)

}

Time Complexity of this program:

• O(n∗m)

• O(logmlogn)

• O(mlogn)

• O(nlogm)

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

• X will always be a better choice for small inputs

• X will always be a better choice for large inputs

• Y will always be a better choice for small inputs

• X will always be a better choice for all inputs