1) Program A and B are analyzed and found to have worst-
case running times no greater than 150nlog2n and n2
respectively.Answer the folloWing questions if possible..
i) which program has the better guarantee on the running
time,for larger values of n(n>10000) ?
ii) which program has the better guarantee on the running
time,for small values of n(n<100) ?
iii) which program will run faster on average for n =1000
2) wRite a program to compute the number of collisions
required in a long random sequence of
insertions using linear probing ,quadratic probing and
double hashing
3) what is the optimal way to compute A1 A2 A3 A4 A5 A6
where the dimensions of the matrices are
A1:10*20 A2 : 20 * 1 A3 : 1 * 40 A4 : 40*5 A5 : 5 * 30
A6 : 30 X 15
- 5 Answers
- 19612 Views
- KPIT, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / achintya singhal
ultimately you will be receiving a matrix of 10*15
A1*A2 give matrix of 10*1
A3*A4 give matrix of 1*5
A5*A6 give matrix of 5*15
therefore use
(A1*A2)*(A3*A4)*(A5*A6)
ALL other will increase the complexity or give matrices of
higher order...
| Is This Answer Correct ? | 8 Yes | 3 No |
Answer / atta un nabi
150nlog2n has an advantage if the value is sufficiently high weather the n^2 has an advantages but in some interval of value that may be smaller then 10000 or not.
according to me if the input size is smaller then 100 it may be exchange their advantages at size 18 or round about it. since n^2 is better.
n^2 is better for average size of 1000.
| Is This Answer Correct ? | 2 Yes | 0 No |
Answer / atta un nabi
for n=1000 n^2 is better in average time complexity.
for n<100 n^2is better.
for n>10000 150nlogn is better.
| Is This Answer Correct ? | 0 Yes | 0 No |
Answer / supra
A belongs to theta(nlogn) class.
B belongs to theta(n^2) class.
Hence at larger inputs,A has a better effeciency
However at smaller inputs say 10,
150*10*1>10*10
Hence B ia better.
But in average case on all inputs, nlogn is always better than n^2.Hence A is better.
For 3) Its all abt matrix compatibility.
First A7=A1*A2(it ll give 10*1 matrix after multiplication)
Next, A8=A3*A4(1*5)
A9=A5*A6(5*15)
Next, A10=A7*A8(10*5). Lastly, A11= A10*A9(10*15)
| Is This Answer Correct ? | 1 Yes | 2 No |
Its clear
150nlog(base-2)n will have advantage on larger inputs
n^2 has advantage on large inputs
But without the exact function we cant estimate the exact
point at which the two graphs exchanges their advantages.
given n>2 log(base-2)n is greater than 1 where as n^2 > 150
only when n>10 so approx it crosses at may be at n=12(Taking
them as exact time complexity not as asymptotic notations)
at 1000 clearly n^2 is better as it is only 10^6 whereas
150nlogn is approx 150*10*10(approx)
| Is This Answer Correct ? | 6 Yes | 10 No |
What is linked list with example?
How does max heap work?
What are the types of sorting?
Does linkedhashset allow duplicates?
In RDBMS, what is the efficient data structure used in the internal storage representation?
Which is faster hashmap or hashset?
Define hashing?
What is collision in data structure?
Is merge sort better than quick?
List some applications of queue data structure.
How many sorting algorithms are there?
How do you search for a target key in a linked list?
Windows 
