Question

Describe an algorithm that, given a set S of n integers and another integer x, determines...

Describe an algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x. Your algorithm must be nlogn. Evaluate how long each step in the algorithm takes to demonstrate that it meets this requirement.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

sort in worst case take O(nlogn)

iterative an take O(n) and searching element in array take O(logn) time
O(n)*O(logn)=O(nlogn)
T(overall)=2*(time for sorting) +time for finding and searching

T(overall)=2*O(nlogn)+O(nlogn)

T(overall)=3*O(nlogn)

T(overall)=O(nlogn)

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Describe an algorithm that takes as input a list of n integers and finds the location...
Describe an algorithm that takes as input a list of n integers and finds the location of the first even integer or returns -1 if there is no even integer in the list. Here is the operation's header: procedure locationOfFirstEven(a1, a2, a3, ..., an : integers)
a. Find an algorithm for solving the following problem: Given a positive integer n, find the...
a. Find an algorithm for solving the following problem: Given a positive integer n, find the list of positive integers whose product is the largest among all the lists of positive integers whose sum is n. For example, if n is 4, the desired list is 2, 2 because 2 × 2 is larger than 1 × 1 × 1 × 1, 2 × 1 × 1, and 3 × 1. If n is 5, the desired list is 2,...
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...
1. Use the roster method to describe the elements of the following set. x∈ℤ||x−3|<12 and x...
1. Use the roster method to describe the elements of the following set. x∈ℤ||x−3|<12 and x is a multiple of 3 2. Use the roster method to describe the elements of the following set. {n∈ℕ∣∣∣1n+6⩾6272 and n is a multiple of 5} 3. Determine the cardinality of the following sets. {x∈ℤ|−4⩽x⩽3}: {x∈ℕ|−4⩽x⩽3}: 4. Evaluate the following expressions. [Hint: start by factoring the polynomial.] ∣∣{x∈ℚ∣∣18x3+69x2+56x=0}∣∣= ∣∣{x∈(0,∞)∣∣18x3+69x2+56x=0}∣∣= ∣∣{x∈ℤ∣∣18x3+69x2+56x=0}∣∣= 5.  Evaluate the following expressions. [Hint: start by factoring the polynomial.] ∣∣{x∈ℝ∣∣x4+11x2+28=0}∣∣= ∣∣{x∈ℚ∣∣x4+11x2+28=0}∣∣= ∣∣{x∈ℕ∣∣x4+11x2+28=0}∣∣= 6....
One way to represent a very large integer (one that won't fit into a variable of...
One way to represent a very large integer (one that won't fit into a variable of type short, int, or even long) is to use an array. The array is of type int, so each element in the array can hold an integer -- we will store just one digit of our number per array element. So if a user entered 2375, it might be stored as -------------------------- | 2 | 3 | 7 | 5 | ... | --------------------------...
Consider the C program (twoupdate) to demonstrate race condition. In this assignment, we will implement Peterson's...
Consider the C program (twoupdate) to demonstrate race condition. In this assignment, we will implement Peterson's algorithm to ensure mutual exclusion in the respective critical sections of the two processes, and thereby eliminate the race condition. In order to implement Peterson's Algorithm, the two processes should share a boolean array calledflagwith two components and an integer variable called turn, all initialized suitably. We will create and access these shared variables using UNIX system calls relating to shared memory – shmget,...
1) Describe an example of each of the following that may be found of your kitchen:...
1) Describe an example of each of the following that may be found of your kitchen: Explain how your choice falls into this category, and if there is a chemical name or symbol for it, provide that as well. Provide a photo of your example with your ID card in it. a) a compound b) a heterogeneous mixture c) an element (symbol) Moving to the Caves… Lechuguilla Caves specifically. Check out this picture of crystals of gypsum left behind in...
Java question, Please answer everything. Thank you Answer the following questions as briefly (but completely) as...
Java question, Please answer everything. Thank you Answer the following questions as briefly (but completely) as possible: What is a checked exception, and what is an unchecked exception? What is NullPointerException? Which of the following statements (if any) will throw an exception? If no exception is thrown, what is the output? 1: System.out.println( 1 / 0 ); 2: System.out.println( 1.0 / 0 ); Point out the problem in the following code. Does the code throw any exceptions? 1: long value...
Please read the article and answear about questions. Determining the Value of the Business After you...
Please read the article and answear about questions. Determining the Value of the Business After you have completed a thorough and exacting investigation, you need to analyze all the infor- mation you have gathered. This is the time to consult with your business, financial, and legal advis- ers to arrive at an estimate of the value of the business. Outside advisers are impartial and are more likely to see the bad things about the business than are you. You should...
Sign In INNOVATION Deep Change: How Operational Innovation Can Transform Your Company by Michael Hammer From...
Sign In INNOVATION Deep Change: How Operational Innovation Can Transform Your Company by Michael Hammer From the April 2004 Issue Save Share 8.95 In 1991, Progressive Insurance, an automobile insurer based in Mayfield Village, Ohio, had approximately $1.3 billion in sales. By 2002, that figure had grown to $9.5 billion. What fashionable strategies did Progressive employ to achieve sevenfold growth in just over a decade? Was it positioned in a high-growth industry? Hardly. Auto insurance is a mature, 100-year-old industry...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT