Analysis of Algorithms

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 possibly small inputs

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

• Y will be a better choice for small inputs

Which of the following is not O(n^2)?

• (15^10) * n + 12099

• n^1.98

• n^3 / (sqrt(n))

• (2^20) * n

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

Consider the following functions:

f(n) = 2^n

g(n) = n!

h(n) = n^logn

Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?

• f(n) = O(g(n)); g(n) = O(h(n))

• f(n) = omega (g(n)); g(n) = O(h(n))

• g(n) = O(f(n)); h(n) = O(f(n))

• h(n) = O(f(n)); g(n) = omega (f(n))

Which of the following is not true about comparison based sorting algorithms?

• The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array

• Radix Sort is taken linear time for sorting

• Counting Sort is not a comparison based sorting algortihm

• Heap Sort is not a comparison based sorting algorithm.

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^2)

• O(nLogn)

• O(n)

• O(nLognLogn)

Consider the above functions

Which of the following is true?

(a) h(n) is 0(f(n))

(b) h(n) is 0(g(n))

(c) g(n) is not 0(f(n))

(d) f(n) is 0(g(n))

• a

• b

• c

• d

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^2)

• Theta (n*Logn)

• Theta (nLognLogn)

What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2.

void fun()

{

int i, j;

for (i=1; i<=n; i++)

for (j=1; j<=log(i); j++)

printf("XYZ");

}

• Θ(n)

• Θ(nLogn)

• Θ(n^2)

• Θ(n^2(Logn))

The time complexity of the following C function is (assume n > 0)

int recursive (int n) {

if(n == 1)

return (1);

else

return (recursive (n-1) + recursive (n-1));

}

• O(n)

• O(n log n)

• O(n^2)

• O(2^n)