Question

**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 ] 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 names in an array of linked
chains**

** [
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 one array element**

** [
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 the last integer in a linked
chain**

** [
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) **

**Searching an array of n items for a particular value by
using a sequential search**

** [
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) **

**Searching an array of n items for a particular value by
using a binary search**

** [
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) **

**Adding an item to a stack of n items**

** [
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) **

**Adding an item to a bag of n items**

** [ 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)**

Answer #1

**Answer :**

**Computing the sum of the first n even integers by using
a for loop : O(n).**

**Displaying all n integers in an array :
O(n).**

**Displaying all n integers in a sorted linked chain :
O(n).**

**Displaying all n names in an array of linked chains :
O(n).**

**Displaying one array element : O(1).**

**Displaying the last integer in a linked chain :
O(n).**

**Searching an array of n items for a particular value by
using a sequential search : O(n).**

**Searching an array of n items for a particular value by
using a binary search : O(log n).**

**Adding an item to a stack of n items :
O(1).**

**Adding an item to a bag of n items : O(1).**

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

#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)
______________________

Given the following list of functions, determine the
order of growth of each using big-Theta notation and put all the
functions in order from slowest-growing to fastest-growing. Be sure
to put functions of equal growth rate on the same level. Unless
otherwise noted, you can assume all logarithms are
base-2.
6nlog(2n)+8n
4n2log(log(8n))+8n2+n
500
n3+7nlog(n2) + 4n
2n+2n+1
log(4n2)+3n+1
12
8log(24n)+10
8n2log(5n2)+7n+200
4log(n3)+1000
100log(16n)log(n6)+23
8nlog(log(n4))+6n+32
9log(log(8n))

Analysing Asymptotic Bounds (Marks: 3)
Prove the following using the definition of asymptotic order
notation.
Example: 15n 3 + 10n 2 + 20 ∈ O(n3 )
Hint: Consider C = 15 + 10 + 20 = 45 and n0 := 1. Then 0 ≤ 12n
3 + 11n 2 + 10 ≤ Cn3 for all n ≥
n0.
a) n 2 + 3n 2 /(2+cos(n)) ∈ O(n
2 )
b) 2n 2 (log n) ∈ Ω(n(log n) 2 )
c)...

Data Structures using C++
Searching a Linked List
Here are the declarations for a simple unsorted linked list of
ints that ends in a null pointer.
//===============================================================
class Cell {
friend class UList;
private:
int data;
Cell* next;
Cell( int dt, Cell* nx=nullptr ) : data(dt), next(nx) {}
};
//===============================================================
class UList {
private:
Cell* head = nullptr; // stationary head
pointer.
Cell* scan =
nullptr; //
for walking down the List.
Cell* follow = nullptr;
public:
void find( int...

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

For each of the following situations, which of the following
ADTs would be most appropriate, and explain (1)
Queue ADT; (2) Stack ADT; (3) Ranked or Positional Sequence ADT;
(4) None of these.
a. The customers at the deli counter who take numbers to mark
their turn.
b. An alphabetic list of names.
c. Integers that need to be sorted.
d. Execution environments of a recursive method.
e. The items on a cash register tape.
f. A word processor that...

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

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

1.Determine the generation time by using the following formula
:
Generation time =∆ t log 2
Log n – log N
Where: N = number of bacteria at a particular time point during
log phase
n = number of bacteria at a second time point during log
phase
∆t = time
(This question was not anwsered in my previos question that i
posted , please help. )
(please check the details and information needed on this
question in my prevoius...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 4 minutes ago

asked 13 minutes ago

asked 14 minutes ago

asked 26 minutes ago

asked 35 minutes ago

asked 44 minutes ago

asked 47 minutes ago

asked 54 minutes ago

asked 56 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago