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





Answers were Sorted based on User's Feedback



1) Program A and B are analyzed and found to have worst- case running times no greater than 150nlog..

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

1) Program A and B are analyzed and found to have worst- case running times no greater than 150nlog..

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

1) Program A and B are analyzed and found to have worst- case running times no greater than 150nlog..

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

1) Program A and B are analyzed and found to have worst- case running times no greater than 150nlog..

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

1) Program A and B are analyzed and found to have worst- case running times no greater than 150nlog..

Answer / vinothkumar.r

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

Post New Answer

More Data Structures Interview Questions

What is time complexity of sorting algorithms?

0 Answers  


How to sort 1 million floating point numbers?

0 Answers  


Is array of data structure?

0 Answers  


Describe avl tree or height balanced binary search tree.

0 Answers  


What do you mean by 2-3-4 tree?

0 Answers  






Why we need cursor implementation of linked lists?

0 Answers  


what is the different between B-tree and B+ tree.

8 Answers   Syntel,


Define a binary tree?

0 Answers  


What is non linear structure?

0 Answers  


What are the basic operations of stack?

0 Answers  


What is static array?

0 Answers  


what is the primary advantage of a linked list?

0 Answers  


Categories