Question

Given an array of n numbers, not necessarily in sorted order, we
wish to find: (i) the range (max - min) and (ii) the interquartile range (IQR) of the numbers.
IQR is defined as the difference between the number at the 25% percentile and the number at the
75% percentile. What is the exact number of comparisons needed for computing the range and
why? Using any algorithm from the chapters of the textbook covered so far as a subroutine, give
an efficient algorithm for computing IQR and analyze its time complexity (you do NOT need to
analyze the subroutine if you remember its time complexity). Show all steps.
(b) Given positive integers, x and n, as input, we wish to compute efficiently the number xn. What
is the size of the input and why? How many multiplications are required by the straightforward
algorithm that initializes an output variable to x and does output = output * x repeatedly until
output = xⁿ. Is this a polynomial-time algorithm? Explain precisely and in detail.

Answer 1

ques A)

To find the range of numbers in a given unsorted array we will require "2*(n-1)" comparisons.

This is because after assigning the value of first element of array, the rest of n-1 elements will be compared to both max and min . thus 2 comparisons for each element, computing to a total of 2*(n-1) comparisons.

now for calculating IQR.

size of array= n

element at 25 percentile= arr[floor(n/4)]

element at 75 percentile= arr[floor(3*n/4)]

IQR= arr[floor(n/4)] - arr[floor(3*n/4)]

Ques.B)

x and n are used as input to calculate x^n .

inputs are integers and its size depends on the plaform used.

for a straightforward algorithm:

output=x;

output=output*x

the no of multiplications will be n-1.

yes this is a polynomial time algorithm.

As there are "n-1" multipliacations. so code will be executed n-1 times. so time complexity will be in the order of n-1.

now, accoding to definiton of big O notation

i.e: any f(x+h) >= g(x) will be written as O(x)

f(n-1)>=g(n)  

so time complexity will be O(n). which is a polynomial time complexity.