Consider the following problem. Given an array A[ 1..n] of integers, test each e
ID: 3599021 • Letter: C
Question
Consider the following problem. Given an array A[ 1..n] of integers, test each element 'alil' in A to see whether it is even or odd. If a' is even, then leave it, otherwise multiply it by 2. (30) (a) (b) (c) (d) Q1. CO2 Write a pseudo-code of the algorithm stated above. (10) Identify and describe the input metric (3) Identify the basic operation. (3) Derive expressions for the best-case and worst-case computational complexity of the algorithm, as a function of the input metric selected. (For the purpose of counting the number ofoperations performed as the indicator of the alaorithm's efficiencv consider addition and subtraction arithmetic operations to be in one class and all the other operations to be in another single class.) (8) Determine the asymptotic expression of the algorithm's efficiency. (6) (e)Explanation / Answer
=========================================================
-------------------------------
(a) PSEUDO CODE:
-------------------------------
STEP1: SIZE OF ARRAY n, INITIALIZE ARRAY A[n]
STEP2: READ ARRAY A[] elements
STEP3: INITIALIZE i=0;
STEP4: WHILE i<n
READ A[i]
CHECK if A[i]%2!=0 WHICH INDICATES A[i] is odd number
A[i] = A[i]*2
STEP5: DISPLAY ARRAY ELEMENTS
------------------------------
(b) INPUT METRIC:
------------------------------
Array size n is the initial input
and ARRAY A[n] elements are the input for array
-------------------------------------
(c) BASIC OPERATION:
-------------------------------------
The operation is that iterate over list of array elements and identify which are odd numbers
using below operation.
% is the operation to be performed inorder to get the reminder
if A[i]%2!=0 operation indicates an ODD number.
------------------------------------
(d) BASIC OPERATION:
-------------------------------------
Time complexity of the algorithm in worst and best case is
O(n)
Since there are n elements present in array
It is required to check each element is even or odd.
In worst case if all the elements are odd
then also the auxillary complexity will be 1
ie O(n)+1 which again equal to O(n).
Hence, time complexity of the algorithm is O(n)
------------------------------------------
(e) Assymptotic expression:
------------------------------------------
Assymptotic expression of the algorithm is if A[i]%2!=0
=========================================================