Please Help. Describe an algorithm that upon input of n real numbers denoted al5

Question

Please Help.

Describe an algorithm that upon input of n real numbers denoted al5 a2: a3 ..., an and another number x: determines which numbers in the list are strictly greater than x. Find the complexity function of the algorithm you described in question 1 above. For each of the following functions, determine whether or not the function is O(x2) and prove your answer. f(x) = 3x + 22 f(x) = -x 2-x+ 100 ftx)= 2x log(x) f(x) = x4/200 f(x) = 3x Represent each of the following graphs with an adjacency matrix.k5 k2,3

Explanation / Answer

(a).

Let us assume that the n real numbers are provided in the form an array

let the numbers in an array of double data type of size n ---> double Array[ n ]

for ( i=0 ; i<n ; i++ )

{

if( Array[ i ] > x )

printf(" %f is strictly grater than x " , Array[ i ]);

}

(b).

In the above algorithm the entire array is traversed one time and the size of the array is equal to 'n'

So , it's complexity is of the order n i.e., O( n )

(c).

a,b,c are of order O(x^2)

d,e are not O(x^2)

(d).

k5

[0, 1, 1, 1, 1]

[1, 0, 1, 1, 1]

[1, 1, 0, 1, 1]

[1, 1, 1, 0, 1]

[1, 1, 1, 1, 0]

k2,3

[0 0 1 1 1]

[0 0 1 1 1]

[1 1 0 0 0]

[1 1 0 0 0]

[1 1 0 0 0]

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---