q1 : i have no idea about kruskal’s algorithm
q2 : please explain it’s ans
q7 : why it’s ans is not 0(nlogn)
q10 : why 2^0(n) < 0(n^3)
q 13 : i have solved , answer should be 0(nlogn)
Doubts: 1, 2 , 7, 10, 13
for q1 you need to first graphs.
for q2 you need to design a stack in such a way that will support the operations in O(1)
We define a variable minEle that stores the current minimum element in the stack. Now the interesting part is, how to handle the case when minimum element is removed. To handle this, we push “2x – minEle” into the stack instead of x so that previous minimum element can be retrieved using current minEle and its value stored in stack.
for q7 If we use binary search then there will be ⌈ Log2(n!) ⌉ comparisons in the worst case, which is Θ(n log n) .But the algorithm as a whole will still have a running time of Θ(n^2) on average because of the series of swaps required for each insertion.
for q10 O(n) has linear time complexity and 2^O(n) would be definately less than O(n3)
you can dry run it using some sample values of n
for q13
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.