I am given a sequential algorithm that does a routine search
on an unordered list. N = 20.
The probability that the value x does NOT appear in the list
is exactly 60%, and the probability that x DOES appear is 40%.
The 3 questions that I could not get were:
A) What is the avg number of element comparisons performed
when n = 20 and x does NOT appear in the List.
(my answer was 20, is this correct?)
B) What is the avg number of element comparisons peformed
when n = 20 and x DOES appear in the list?
C) What is the avg number of element comparisons performed
when n = 20. This should be a single number answer they said.
- 3 Answers
- 5608 Views
- I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / guest
a) 20 worst case scenario so it will take N comparison
b) 10 average case scenario N/2 omparisons
c) 16 (20*0.6 + 10*0.4 = 16) as stated above
| Is This Answer Correct ? | 17 Yes | 1 No |
Answer / ranjit
The second answer is partially correct.
a) 20. It will take 20 comparisons to determine that x does not appear in the unordered list of size N.
b) Assuming that x is equally likely to be in any of the 20 positions in the list, the average number of comparisons will be (1 + 2 + ... + 20)/20 = 10.5.
c) 20*0.6 + 10.5*0.4 = 16.2
| Is This Answer Correct ? | 9 Yes | 0 No |
Answer / bond
A) What is the avg number of element comparisons performed
when n = 20 and x does NOT appear in the List. (my answer
was 20, is this correct?)
è I guess 12.
B) What is the avg number of element comparisons peformed
when n = 20 and x DOES appear in the list?
è I guess 8.
C) What is the avg number of element comparisons performed
when n = 20. This should be a single number answer they
said.
è I guess 8.
| Is This Answer Correct ? | 5 Yes | 10 No |
What do you know about different sorting algorithms?
why boundary tag representation is used?
Which is faster arraylist or hashmap?
Reverse a linked list from the middle.
Can we add duplicate keys in a hashmap?
Is pointer a variable?
Can hashmap be sorted?
Define linear probing?
What actions are performed when a function is called?
What is the data structures used to perform recursion?
What is sorting an array?
Which interfaces are implemented by linkedhashset?
Windows 
