### appro's blog

By appro, 20 months ago, ,

What is the time complexity for Miller Rabin Primality Test?

write n − 1 as 2^r·d where d is odd.

WitnessLoop: repeat k times: //runs k times.

{ pick a random integer a in the range [2, n − 1]

x ← a^d mod n

if x = 1 or x = n − 1 then

continue WitnessLoop

repeat r − 1 times:               //r=O(logn)

{

x ← x^2 mod n               //TC=O(logn)

if x = 1 then

return composite

if x = n − 1 then

continue WitnessLoop

}

return composite

}

return probably prime

According to me the worst case time complexity would be O(k*(logn)^2)? But the wikipedia page mentions it as

O(k*(logn)^3). Can anyone help me out?

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

•
• +12
•

By appro, history, 2 years ago, ,

I am given an array A of size n. I have to answer q queries of the form [Li,Ri]

Answer to the query [Li,Ri] is the minimum of all A[x] for all x from [Li,Ri].

1≤n,q≤10^5 , 1≤Ai≤10^9

Segment Tree implementation of the input array gets us the complexity of O(n) for creating the segment tree and O(log(n)) for queries. Overall Complexity- O(n+qlog(n))

Complexity for creating cartesian tree is O(n) and then for range queries we need to find the LCA of the 2 indices and the complexity for that is O(log(n)) Overall Complexity-O(n+qlog(n))

The segment tree implementation is doing good. But I am getting Time Limit Exceeded in the Cartesian Tree Implementation. Can anyone explain me the reason behind this?

•
• -8
•

By appro, history, 2 years ago, ,

What is the time complexity for building a segment tree for an array of size n?