Question

#data structures

Give the appropriate execution time efficiency of the following
array algorithms using Big-O notation. Assume the size of the array
is n.

a) Linear Search (average case) ______________________

b) Binary Search (worst case)
______________________

c) Insertion Sort (best case)
______________________

d) Insertion Sort (average
case)
______________________

e) Quick Sort (average case)
______________________

Answer #1

**Part a)**

**Linear Search ( Avg Case ) :** In this we
traverse the array element by element and we compare each with the
element that need to be searched . So In average case we say that
element is found in between the array . The number of elements
traversed are n/2 .

**So Time taken in O(n)**

**Part b)**

**Binary Search ( Worst Case ) :** Here we compare
middle element with the element that need to be searched and then
if element is less then we traverse the left sub array else right
sub array .

**So Time Taken is O(logn)**

**Part c)**

**Insertion Sort (Best case ) :** The best case is
when array is already sorted and then we apply insertion sort so no
swapping is needed .

**Hence Time Taken in O(n)**

**Part d )**

**Insertion Sort ( Avg case ) :** Average case
arrives when some times we have to do so swapping while we do the
new insertion while other times we have to swap it with all the
elements present to put the its correct position .

**So Time Taken in O(n^2)**

**Part e )**

**Quick Sort ( Avg case ) :**Average case arrives
when some times we have elements sorted around the pivot while
other times we have to sort them to get the pivot in appropriate
position

**So Time Taken in O(nlogn)**

This is how each algorithm runs in various cases

**Thank You**

**If u like the answer then do Upote it and have any doubt
drop in comments**

Fill in the following table, using Big-O notation to give the
worst and average-case times for each of the stack methods for a
stack of size N.
OPERATION
WORST-CASE TIME
AVERAGE-CASE TIME
constructor
empty
size
push
pop
peek

Suppose an array A stores n integers, each of which is in {0, 1,
2, ..., 99}. Which of the following sorting algorithms can sort A
in O(n) time in the worst case?
Question 16 options:
A)
merge sort
B)
counting sort
C)
quicksort
D)
None of these options is correct.
E)
insertion sort

Using Big O notation, indicate the time requirement of
each of the following tasks in the worst case.
Computing the sum of the first n even integers by using
a for loop
[
Choose ] O(1) O(2n) O(n*log n ) O(2^n) O(log n) O(n^2) O(n) O(2)
O(n^3)
Displaying all n integers in an array
[
Choose ] O(1) O(2n) O(n*log n ) O(2^n) O(log n) O(n^2) O(n) O(2)
O(n^3)
Displaying all n integers in a sorted linked
chain
[
Choose...

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...

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...

What is the worst-case time (in Big-O) for building a Min-Heap
of N nodes, using bulk insertion
(bottom-up construction), assuming comparing two
keys takes constant time. Justify your answer. You may assume N =
2h+1 – 1, for simplicity.

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 =...

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
------...

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...

Please answer the following Case
analysis questions
1-How is New Balance performing compared to its primary rivals?
How will the acquisition of Reebok by Adidas impact the structure
of the athletic shoe industry? Is this likely to be favorable or
unfavorable for New Balance?
2- What issues does New Balance management need to address?
3-What recommendations would you make to New Balance Management?
What does New Balance need to do to continue to be successful?
Should management continue to invest...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 19 minutes ago

asked 25 minutes ago

asked 25 minutes ago

asked 26 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 3 hours ago

asked 3 hours ago

asked 3 hours ago