Question

Restricted structures such as stack and queue are fast, but they do not support access in the key field mode.

Group of answer choices

True

False

Big O analysis evaluates an algorithm based on its _________ performance.

Group of answer choices

A. average-case

B. best-case

C. worst-case

Which of the following algorithms is the fastest in speed?

Group of answer choices

A. Polynomial time algorithm

B. Linear time algorithm

C. Exponential time algorithm

The following code gives an implementation of searching an item in a given array.

public static int search(int arr[], int x)
{
    int n = arr.length;
    for(int i = 0; i < n; i++)
    {
        if(arr[i] == x)
            return i;
    }
    return -1;
}

What is the time cost of the above block of code in Big O analysis?

Group of answer choices

A. O(1)

B. O(n)

C. O(nlog_2 n)

The following code gives an Java implementation of binary search.

int binarySearch(int arr[], int x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        }  
        return -1; 
    } 

What is the time cost of the above algorithm in terms of Big O notation?

Group of answer choices

A. O(n)

B.O(log_2 n)

C.O(nlog_2 n)

Suppose we use the sequential search algorithm to fetch an element from an array of 1024 elements, what are the minimum and the maximum number of comparisons in the searching loop?

Group of answer choices

A. Minimum 1, Maximum 10

B. Minimum 1, Maximum 1024

C. Minimum 10, Maximum 1024

Answer 1

1) True

Key field mode is not supported in Restricted structures

2) Worst Case

It is an upper bound of an algorithm, it bounds a function only from above i.e the worst case scenario.

3) Linear time algorithm

Since time taken by any polynomial or exponential function will be greater than linear time complexity.

Time Complexity: linear<polynomial<exponential

Therefore Linear time algorithm will be the fastest like O(n).

4) O(n)

SInce there is only one loop that runs n times, so Big O analysis will give O(n).

5) O(log_2 n)

The time complexity of Binary Search is O(log₂ n).

6) Minimum 1, Maximum 1024

For a sequential search the minimum will be when element is found at the first place and maximum when it is at the last, so min=1 and max=1024

__________________________________________________________________________________

**Please Upvote :)