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
- 5611 Views
- I also Faced
- E-Mail Answers
Answer Posted / 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 |
Post New Answer View All Answers
Tell me is it better to use a pointer to navigate an array of values, or is it better to use a subscripted array name?
Define balance factor of a node in avl tree?
What is structured data with example?
Define a complete binary tree?
Run time memory allocation is known as in data structure?
How is the front of the queue calculated in data structure?
What is a hashmap in c?
What is the use of sorting the data?
Is array of data structure?
What are the 3 types of variables?
Is it possible to make an array volatile in java?
What is a directed graph?
Is array part of collection framework?
What are hash tables good for?
Who invented data structure?
