Let a1 a2 an be a sequence of positive integers a Describe

Let a_1, a_2, ..., a_n be a sequence of positive integers. (a) Describe an algorithm for finding the location of the largest even integer in the sequence. (b) Let f(n) be the number of operations in your algorithm obtained from (a). Express f(n) in terms of n and then use a big-O to estimate f(n).

Solution

a)

Algorithm Find_Largest_Even()

consider sequence of numbers are stored in an array

Initialize variable to find the maximum. max=0

For i =0 to Array.Length

If Array[i]%2 = 0 Then

If Array[i] > Array[max]

max=i

End If

End If

End For

return max

End Algortihm

b)

Here we need to calculate the number of times each instruction is executed and need to represent this time complexity interms of Big-O notation

Now in the above given algorithm

Algorithm Find_Largest_Even()

consider sequence of numbers are stored in an array

Initialize variable to find the maximum. max=0 ( 1 time)

For i =0 to Array.Length ((Array.length let =n )+1times)

If Array[i]%2 = 0 Then (n times)

If Array[i] > Array[max] (<=n times)

max=i (<= n times)

End If

End If

End For

return max

End Algortihm

Hence by adding the individual instructions time to find the total time we get

1+(n+1)+(n)+(n)+(n)+(n)+(n)+(n)+(1)

=7n+1

this can be represented as O(n) , This is the time complexity of the given prescribed algorithm