Question

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

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

Homework Answers

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(log2 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 :)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
Do a theta analysis and count the number of computations it performed in each function/method of...
Do a theta analysis and count the number of computations it performed in each function/method of the following code: import java.io.*; import java.util.Scanner; class sort { int a[]; int n; long endTime ; long totalTime; long startTime; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public sort(int nn) // Constructor { a = new int[nn]; n = nn; endTime= 0; totalTime =0; startTime =0; } public static void main(String args[]) throws IOException { System.out.print("\nEnter number of students: "); int nn =...
Analyze the worst case running time of the following code in “big-Oh” notation in terms of...
Analyze the worst case running time of the following code in “big-Oh” notation in terms of the variable n. a. void fdisp1(int n) { for(int i=0; i < n; i++) { for(int j=0; j < n; j++) { for(int k=0; k < n; k++) { for(int m=0; m < n; m++) { System.out.println("Hi I am Here"); } } } } } b. voidprintAllPossibleOrderedPairs(intarr[], int size) { for (int i = 0; i < size; i++) { for (int j =...
Complete this function (the instructions are below the code): private static int numCommonElements(int A[], int B[],...
Complete this function (the instructions are below the code): private static int numCommonElements(int A[], int B[], int lenA, int lenB) { // Complete this function. } We want to solve the following problem: given two sorted arrays A[n] and B[m] of length n and m respectively, we want to nd the number of elements that are common to both the arrays (without repeated counting of the same element). For example, the arrays A[ ] = {7; 13; 19; 20; 22;...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
Write a program of wordSearch puzzle that use the following text file as an input. The...
Write a program of wordSearch puzzle that use the following text file as an input. The output should be like this: PIXEL found (left) at (0,9). ( Use JAVA Array ) .Please do not use arrylist and the likes! Hints • The puzzle can be represented as a right-sized two-dimensional array of characters (char). • A String can be converted into a right-sized array of characters via the String method toCharArray. . A word can occur in any of 8...
Q1: Thefollowing code is supposed to return n!, for positive n. An analysis of the code...
Q1: Thefollowing code is supposed to return n!, for positive n. An analysis of the code using our "Three Question" approach reveals that: int factorial(int n){ if (n == 0)     return 1;   else     return (n * factorial(n – 1)); } Answer Choices : it fails the smaller-caller question.     it passes on all three questions and is a valid algorithm.     it fails the base-case question.     it fails the general-case question. Q2: Given that values is of...
A Queue is a linked list with pointers to both the head of the list as...
A Queue is a linked list with pointers to both the head of the list as well as the tail (or the last element) of the list. Given a queue Q, Q.head gives the head of the queue and Q.tail gives the tail of the queue. Give O(1) time algorithms for the following tasks. Enqueue • Input: A queue Q of distinct integers and a queue element a not in Q. 1 • Output: Q with the element a added...
a) Please Select All That Apply: What are the possible applications of Priority Queue?      CPU Scheduling...
a) Please Select All That Apply: What are the possible applications of Priority Queue?      CPU Scheduling All queue applications where priority is involved.               kernel of NT for keep track of process information b) Running Time Analysis: Give the tightest possible big-O upper bound for the worst case running time for each operation listed below in terms of N. Assume no duplicate values and that you can implement the operation as a member function of the class – with access to...
Given the recursive bubble sort algorithm, analyze its time complexity in terms of Big O. bubbleSort(A[],...
Given the recursive bubble sort algorithm, analyze its time complexity in terms of Big O. bubbleSort(A[], n) { // Base case if (n == 1) return;    // One pass of bubble sort. After // this pass, the largest element // is moved (or bubbled) to end. for (i=0; i<n-1; i++) if (A[i] > A[i+1]) swap(A[i], A[i+1]);    // Largest element is fixed, // recur for remaining array bubbleSort(A, n-1); }
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT