Analysis of Algorithm 2-Quizz(0)

The complexity of Binary search algorithm is

• O(n)

• O(log n)

• O(n2)

• O(n log n)

What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > i; j--) {

a = a + i + j;

}

}

• O(N)

• O(N*log(N))

• O(N * Sqrt(N))

• O(N*N)

A linear function takes the form

• f(n) = an + b

• f(n) = an2 +bn + c

• f(n) = alog2n

• f(n) = a + b

The number of executions grows extremely quickly as the size of the input increases

• Exponential Time

• Linear Time

• Polynomial Time

• Constant Time

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

Consider this list of numbers: 3 4 6 7 8 9. If the number 9 was to be found using a linear search, how many comparisons need to be made?

• 6
• 3
• 8
• 4

What is the main disadvantage of a binary search compared to a linear search?

• It requires the data to be in order
• It requires more memory
• It does not execute as quickly with larger data sets
• Not all CPUs are capable of executing the algorithm

asymptotic notations represents

• space complexity of algo

• time complexity of algo

• both a and b

• none of the above

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)

it is usually easier and clearer to use something that comes somewhere in between formatted English and computer program code, but is not runnable because certain details are omitted.

• Algorithm

• Algorithm Analysis

• Pseudocode

• Flowchart