Consider an array A of n>=2 distinct unsorted numbers. Design a t(n)=f(n) algori

Question

Consider an array A of n>=2 distinct unsorted numbers. Design a t(n)=f(n) algorithm to determine how many numbers are between any two numbers x and y that are known to be in A. The term between refers to the positions that occur from the position after the one in which x is located to the position before that in which y is located. Note that x and y may be anywhere in the array. Provide logically sound pseudocode and analysis that shows it is O(n).

Numbers in A: 22 3 11 4 8 12 89 1 54 15 7 9 2 44 21

examples: let x = 11, y = 15; there are 6 numbers between x and y

let x = 9, y = 4. There are 7 numbers between x and y

Explanation / Answer

Let me know if you have any doubt. Please give thumbs up, If it is helpful for you. Thankyou!!

Pseudocode:

START
INITIALIZE x,y,count,pos
INITIALIZE A[]={ 22 3 11 4 8 12 89 1 54 15 7 9 2 44 21}
SET count=0
DISPLAY "Enter the first value"
READ x
DISPLAY "Enter the second value"
READ y
FOR i=0 to A.length()-1
   IF A[i]==x
       pos=i
       break
   END IF
END FOR

FOR i=pos to A.lenght()-1
   IF A[i]!=y
       count+=1
   ELSE
       break
   END IF
END FOR
DISPLAY "The total numbers present in between given numbers are" count
STOP

Analysis:

I have used two loop:
one to find out the position of first element which will take O(n).
other is to count how many elements between two siven numbers. This will also take O(n).

So total complexity: O(n) + O(n) ==> O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects