Explore BrainMass

Runtime Analysis of Search Algorithm

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Consider searching algorithms on the following array of data:
[22 21 9 4 16 2 10 14 20 31 26 19 17 28 8 13]

Suppose you want to implement a searching algorithm to see if the data set contains the number 19. Demonstrate how the search would go if you used:

A sequential search
A binary search
State the runtime for each of the searches, in this example, and for general data sets of size n. Address the issue of the order of the data in binary searching.
Suppose an algorithm that processes a data set of size 8 has a runtime of 72, and the same algorithm on a data set of size 20 has a runtime of 420. Using big-O notation, state the runtime for this algorithm for the general case of a data set of size n.
Suppose you develop an algorithm that processes the first element of an array (length of n), then processes the first 2 elements, then the first 3 elements, and so on, until the last iteration of a loop, when it processes all elements. Thus, if n = 4, the runtime would be 1 + 2 + 3 + 4 = 10.

Create a table that depicts the runtime for arrays of length 1 to 10. Would you expect the general runtime to be O(n), O(n2), O(n3), or some other function of n? Explain.

© BrainMass Inc. brainmass.com October 25, 2018, 6:20 am ad1c9bdddf

Solution Preview

A sequential search of the array for the number 19 would go through each element of the array starting with the first until the number 19 was found. The runtime for this algorithm is O(n), where n is the size of the array.

A binary search would involve first sorting the array, which can be done in time O(log n), and then ...

Solution Summary

We analyze the runtime of a seqential search and binary search algorithm.

See Also This Related BrainMass Solution

Research Works for Satellite Route Optimization.

The Satellite Mission Scheduling problem with Dynamic Tasking (SMS-DT) involves scheduling tasks for a satellite, where new task requests can arrive at any time, non-deterministically, and must be scheduled in real-time. The schedule is a time ordered sequence of activities (scheduled tasks) to be performed by the payload of a satellite. Each activity has a start time and duration. The duration of an activity is a function of its start time: it can be calculated based on such factors as target size, task type, and geometry (between target and satellite, or due to lighting conditions). The transition time between activities is instantaneous, provided the targets lie within the field of view of the payload.
In addition, the Satellite Mission Scheduling problem is priority based: a lower priority task should not adversely impact a higher priority task. A lower priority activity could cause a higher priority activity move to a new location on the schedule, but cannot bump the higher priority activity off of the schedule. However, a higher priority activity could bump a lower priority activity off of the schedule in order for it to get on the schedule. A priority of 0 (zero) is highest and a priority of 999 is lowest. Given a choice, it is preferable to complete a task as early as possible.
I have researched on monotonic algorithm and genetic algorithm. I would like to know what other algorithms are used in the past for this problem. And what are the pros and cons of them? Why do we still need to find or develop new or hybrid algorithm for this problem? Thank you.

View Full Posting Details