DISCRETE MATHS - ALGORITHMS 3.1 - ALGORITHMS 1) Use the linear search to find th

Question

DISCRETE MATHS - ALGORITHMS

3.1 - ALGORITHMS

1) Use the linear search to find the element 55 in the list: 61 62 83 55 47 50 33. How many steps were required?

3.2 - THE GROWTH OF FUNCTIONS

1) Determine whether the function f(x) = x2 + 5 x + 7 is O(x^2).
2) Give a big-O estimate for the function f(x) = 3 x4 + 4 x2 - 7 x + 5.
3) Give a big-O estimate for each the function. For the function g in the estimate that f(x) is O(g(x)), use a simple function g of the smallest order.
2^n (n^3 + 3 n)

4) Determine whether the function f(x) = x^2 + 5 x + 7 is (x^2).
5) Show f(x) = x^2 + 5 x + 7 is (x^2).
6) Give the order of the polynomial 2 x^5 - 7 x^3 + 8 x - 1.

3.3 - COMPLEXITY OF ALGORITHMS

1) Describe the time complexity of the max algorithm (Algorithm 1 from Section 3.1) by counting the number of comparisons.
2) Describe the time complexity of the bubble sort algorithm in terms of the number of comparisons used (and ignore the time to compute i or j in each iteration of the loop in the algorithm).

Explanation / Answer

Excercise 3.1 :

In linear search,target value is compared with each element of the list, untill it is found or untill all elements are searched. So, if there are n elements in the list, it takes almost n operations in such search but in case of equally likely elements , it takes as an average n/2 operations.

LEt list be A and 55 is denoted by letter N, then below steps are followed in searching the value 55 :

1) set i to 0 (where i is the counter)

2) If Ai=N, search terminates and returns i.

3) i=i+1

4) If i < 7 (as there are 7 elements), repeat step 2.

5) Search terminates unsuccessfully.

So, in first three steps, 55 will be compared with 61,62 and 83 and at fourth step, it founds the right match.

Answer

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.