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 _{2}
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
:)*

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 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 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[], 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 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 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 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 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
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[], 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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 3 minutes ago

asked 11 minutes ago

asked 16 minutes ago

asked 25 minutes ago

asked 36 minutes ago

asked 38 minutes ago

asked 39 minutes ago

asked 41 minutes ago

asked 41 minutes ago

asked 42 minutes ago

asked 47 minutes ago

asked 50 minutes ago