高数作业代写 Discrete Mathematics and Its Applications

Workshop 2

Exercise 3

高数作业代写 There will be  iterations, in each iteration, 2 comparisons will be run. Then the next one will be comparing  to end the while iteration

a)

The linear search algorithm at worst case will not find the target in the list. So i will go from 1 to n+1, and there will be n+1 comparisons when affirming  , And in the first n steps,  will be tested. In the n+1 step, condition  is not met, therefore the equality is not tested.

Then when returning the index, another  is executed, therefore total number of comparison is:  高数作业代写

An example input can be a = [1,2,3,4,5], x = 8

b)  高数作业代写

Let  denote the average number of comparisons for an input of size n. In a) we already showed that in worst case scenario the number of comparison is 2n+2. In other cases, the number of comparisons will be smaller than 2n+2. Therefore we have:

For an average case, n/2 elements will examined before we find the target, there will be at least (n/2) * 2 = n comparisons. Therefore  . So we have:

c)

i)

The full iteration of the while loop will first compare , then it will compare . Therefore the iteration executes 2 comparisons.

ii)

For the first iteration, , and

iii)

If we found out  then i = m + 1 for the next iteration, we will drop the first halve of the elements. Otherwise we will drop the second halve by setting j = m

iv)

Each time half the elements in the list will be excluded, suppose we need to exclude k times to find the last one element, then:  高数作业代写

So we need to exclude  times.

v)

There will be  iterations, in each iteration, 2 comparisons will be run. Then the next one will be comparing  to end the while iteration, and the final comparison is .

In short there will be:

comparisons.

d)  高数作业代写

Let  be the average number of comparisons needed for input size of n, the recurrence relation is:

Note that , so we have: , therefore, the solution to this recurrence equation is:

e)

Need results from last part

Compare these theoretical results with the results you got from your implementation

f)  高数作业代写

i)

In linear search, i will go from 1 to 10001, and there will be 10001 comparisons when affirming  , And in the first 10000 steps,  will be tested for m=7 times for each target element. In the n+1 step, condition  is not met, therefore the equality is not tested.

In total there will be 10001 + 10000 * 7 = 80001 comparisons. This is .

ii)

Once sorted, we can use binary search 7 times to find all 7 numbers. The time complexity is: 高数作业代写

iii)

When  we will see the two approaches have similar complexity. When  it's better to sort the arrays first.

更多代写：计算机作业代写    经济代考   essay代写      AI作业代做  论文代写费用