DAA Quiz 1

What is time complexity of fun()?

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²)

• O(nLogn)

• 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)

The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n disc’s is

• T(n)=2T(n–2)+2

• T(n) = 2T(n – 1) + n

• T(n)=2T(n/2)+1

• T(n) = 2T(n – 1) + 1

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

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

f1(n) = 2^n

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

f3(n) = nLogn

f4(n) = n^(Logn)

• f3, f2, f4, f1

• f3, f2, f1, f4

• f2, f3, f1, f4

• f2, f3, f4, f1

What is the best case time complexity of fun()?

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)

• O(n²)

• O(nlogn)

• O(n(logn)²)

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)

Let T(n) be a function defined by the recurrence

T(n)=2T(n/2)+√n

T(1) = 1

Which of the following statements is TRUE?

• T(n) = θ(log n)

• T(n) = θ(√n)

• T(n) = θ(n)

• T(n) = θ(n log n)

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)

. 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

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

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

• Y will be a better choice for small inputs