(1) In calculating the time complexity, 1000n3 is asymptotically bigger than (a) 2n , (b) 10n3...
(1) In calculating the time complexity, 1000n3 is asymptotically bigger than (a) 2n , (b) 10n3 , (c) (log ?)n3 , and (d) 10000n2 .
(2) For any sorting algorithm using a comparison between pairs of elements on n elements, what is the lower bound for the number of required comparisons?
(a) ?(n2 ), (b) Ω(? log ?), (c) Ω(?), and (d) none of the above.
Homework Answers
1 --> c
2--> Ω(nLog2n)
n! <= 2^x Taking Log on both sides. log2(n!) <= x Since log2(n!) = Θ(nLogn), we can say x = Ω(nLog2n)
Add Answer to:
(1) In calculating the time complexity,
1000n3 is asymptotically bigger than (a)
2n , (b) 10n3...
1. Give an asymptotically tight bound to each of the following expressions: 3n^2 + 2n^3 3n...
1. Give an asymptotically tight bound to each of the following expressions: 3n^2 + 2n^3 3n log n + 2n^2 2^n + 3^n 2. Arrange the following asymptotic family from lower order to higher order. The first has been done for you. O(n log n) O(n^3) O(log n) O(n^2 log n) O(n) O(3^n) O(2^n) 3. At work, Peter needs to solve a problem of different sizes. He has two algorithms available to solve the problem. Algorithm A can solve the...
Solve ques no. 2 a, b, c, d . Algorithm 1 Sort a list al,..., an...
Solve ques no. 2 a, b, c, d .
Algorithm 1 Sort a list al,..., an for i=1 to n-1 do for j=1 to n-i do if aj > aj+1 then interchange a; and a;+1 end if end for end for (b) Algorithm 1 describes a sorting algorithm called bubble sort for a list al,...,an of at least two numbers. Prove that the algorithm is complete, correct and terminates. (2) Complexity of Algorithms (Learning Target C2) (a) What is the...
if possible solve part d in detail. a) fi(n) n2+ 45 n log n b) f:(n)-1o+...
if possible solve part d in detail.
a) fi(n) n2+ 45 n log n b) f:(n)-1o+ n3 +856 c) f3(n) 16 vn log n 2. Use the functions in part 1 a) Isfi(n) in O(f(n)), Ω(fg(n)), or Θ((6(n))? b) Isfi(n) in O(f(n)), Ω(f,(n)), or Θ((fs(n))? c) Ísf3(n) in O(f(n)), Ω(f(n)), or Θ(f(n))? d) Under what condition, if any, would the "less efficient" algorithm execute more quickly than the "more efficient" algorithm in question c? Explain Give explanations for your answers...
a) Prove that running time T(n)=n3+30n+1 is O(n3) [1 mark] b) Prove that running time T(n)=(n+30)(n+5)...
a) Prove that running time T(n)=n3+30n+1 is O(n3) [1 mark] b) Prove that running time T(n)=(n+30)(n+5) is O(n2) [1 mark] c) Count the number of primitive operation of algorithm unique1 on page 174 of textbook, give a big-Oh of this algorithm and prove it. [2 mark] d) Order the following function by asymptotic growth rate [2 mark] a. 4nlogn+2n b. 210 c. 3n+100logn d. n2+10n e. n3 f. nlogn
JAVA What is the complexity of this algorithm? Assign each student in the class a number...
JAVA What is the complexity of this algorithm? Assign each student in the class a number from 1 to n, where n is the number of students. Then ask each of the odd-numbered students whether he or she is left-handed. a. O(1) b. O(n) c. O(n ^ 2) d. O(log n) What is the complexity of this algorithm? In a very difficult CS class, half the n students who originally signed up drop the course after the first quiz. After...
1. What is the worst case time complexity of insertion into a binary search tree with...
1. What is the worst case time complexity of insertion into a binary search tree with n elements? You should use the most accurate asymptotic notation for your answer. 2. A binary search tree is given in the following. Draw the resulting binary search tree (to the right of the given tree) after deleting the node with key value 8. 10 3. You have a sorted array B with n elements, where n is very large. Array C is obtained...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an) (a) Describe in English...
Consider the following pseudocode: Algorithm RecursiveFunction (a, b) // a and b are integers if (as1...
Consider the following pseudocode: Algorithm RecursiveFunction (a, b) // a and b are integers if (as1 ) return b; else return RecursiveFunction (a-2, a/2); endif a. What is the time complexity of the RecursiveFunction pseudocode shown above? b What is the space complexity of the RecursiveFunction pseudocode shown above? n(n+1) C. What is the time complexity of the following algorithm (Note that 21-, i = n(n+1)(2n+1). and Σ.,1 ): Provide both T(n) and order, Ofn)). int A=0; for (int i=0;i<n;i++)...
Part A Analyze the following recurrences and show their time complexity functions using (I) iteration method...
Part A Analyze the following recurrences and show their time complexity functions using (I) iteration method and (2) Master Theorem. AI. T(n) = 2T 3 A2. T(n) = 3T 2n АЗ. Т(п) — Т(п — 2) + 3 А4. Т(п) — 2Т (п — 1) + 1 A5. T(n)= 4T +n log n A6. T(n) = 3T +n log n n2 A7. T(n) = 27 Part B Do 2.3-4 (р39) and Problem 2-1 (р39) Part C Implement MERGE-SORT() algorithm that...
A skip list is a data structure that allows Oflog n) search complexity as well as O(log n)insertion complexity within an ordered sequence of n elements. A skip list is built in layers. Each layer is...
A skip list is a data structure that allows Oflog n) search complexity as well as O(log n)insertion complexity within an ordered sequence of n elements. A skip list is built in layers. Each layer is a linked list. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer L appears in layer L+1 (higher layer) with some fixed probability p. A search for...
Solve ques no. 2 a, b, c, d .
Algorithm 1 Sort a list al,..., an for i=1 to n-1 do for j=1 to n-i do if aj > aj+1 then interchange a; and a;+1 end if end for end for (b) Algorithm 1 describes a sorting algorithm called bubble sort for a list al,...,an of at least two numbers. Prove that the algorithm is complete, correct and terminates. (2) Complexity of Algorithms (Learning Target C2) (a) What is the...
if possible solve part d in detail.
a) fi(n) n2+ 45 n log n b) f:(n)-1o+ n3 +856 c) f3(n) 16 vn log n 2. Use the functions in part 1 a) Isfi(n) in O(f(n)), Ω(fg(n)), or Θ((6(n))? b) Isfi(n) in O(f(n)), Ω(f,(n)), or Θ((fs(n))? c) Ísf3(n) in O(f(n)), Ω(f(n)), or Θ(f(n))? d) Under what condition, if any, would the "less efficient" algorithm execute more quickly than the "more efficient" algorithm in question c? Explain Give explanations for your answers...
1. What is the worst case time complexity of insertion into a binary search tree with n elements? You should use the most accurate asymptotic notation for your answer. 2. A binary search tree is given in the following. Draw the resulting binary search tree (to the right of the given tree) after deleting the node with key value 8. 10 3. You have a sorted array B with n elements, where n is very large. Array C is obtained...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an) (a) Describe in English...
Consider the following pseudocode: Algorithm RecursiveFunction (a, b) // a and b are integers if (as1 ) return b; else return RecursiveFunction (a-2, a/2); endif a. What is the time complexity of the RecursiveFunction pseudocode shown above? b What is the space complexity of the RecursiveFunction pseudocode shown above? n(n+1) C. What is the time complexity of the following algorithm (Note that 21-, i = n(n+1)(2n+1). and Σ.,1 ): Provide both T(n) and order, Ofn)). int A=0; for (int i=0;i<n;i++)...
Part A Analyze the following recurrences and show their time complexity functions using (I) iteration method and (2) Master Theorem. AI. T(n) = 2T 3 A2. T(n) = 3T 2n АЗ. Т(п) — Т(п — 2) + 3 А4. Т(п) — 2Т (п — 1) + 1 A5. T(n)= 4T +n log n A6. T(n) = 3T +n log n n2 A7. T(n) = 27 Part B Do 2.3-4 (р39) and Problem 2-1 (р39) Part C Implement MERGE-SORT() algorithm that...
A skip list is a data structure that allows Oflog n) search complexity as well as O(log n)insertion complexity within an ordered sequence of n elements. A skip list is built in layers. Each layer is a linked list. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer L appears in layer L+1 (higher layer) with some fixed probability p. A search for...
Most questions answered within 3 hours.
-
Assume Kw = 1.01 ✕ 10−14
For pure water, we can calculate [H3O+ ] = [OH...
asked 45 minutes ago -
Suppose that on a temperature scale X, water boils at 203.0°X
and freezes at -105.7°X. What...
asked 1 hour ago -
BaS crystallizes in a cubic unit cell with S2- ions on each
corner and each face....
asked 2 hours ago -
A. 0≤P(Oi)≤10≤P(Oi)≤1 for each i
B. P(Oi)≤0P(Oi)≤0
C. P(Oi)=1+P(OCi)P(Oi)=1+P(OiC)
D. P(Oi)≥1P(Oi)≥1
If an experiment consists of...
asked 3 hours ago -
A battery has an emf of 9.20V and an internal resistance of 1.20
ohm. a)What resistance...
asked 3 hours ago -
The area of an elastic circular loop decreases at a constant
rate, dA/dt = −6.60×10−3 m2/s...
asked 4 hours ago -
The denaturation of proteins can be described by the
equilibrium
F⇌U
where F and U represent...
asked 6 hours ago -
Please answer what the maximum and minimum force is, and the
angle on the ion is...
asked 6 hours ago -
implement a program that reads a number of rows and a symbol.
The program will draw...
asked 6 hours ago -
Assume that when adults with smartphones are randomly selected,
45% use them in meetings or classes....
asked 6 hours ago -
Determine the number of formula units of
Na2SO4 and moles of oxygen contained in 8.11
moles...
asked 6 hours ago -
Explain in steps on the following code
What would be the output when executed
using System;...
asked 6 hours ago