Analysis of complexity of two solutions to T-Primes

Правка en1, от ghoshsai5000, 2017-06-26 10:25:30

So, I adopted two different approaches to the problem T-Primes ...

In the first solution, I maintained a set of all squares of Primes ... So, the complexity should be O(D log log D + N log S),

Where D = 1e6, N is the number of queries and S is the size of the set ... Each query on a set takes O(log S) time at most because it is a balanced tree.

In the second solution, I only maintained a vector of primes and checked if a number is a square root and if the square root is prime.

Here the solution is O(D log log D + T), where T is the complexity of finding square root of T ... I am unable to analyse ...

I know finding N^2 is easier than finding root(N) ... Can someone explain why one solution is better than the other ?

Help in understanding the complexities of the solutions would be much appreciated !

Теги algorithm complexity, analysis, numbertheory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ghoshsai5000 2017-06-26 10:25:30 994 Initial revision (published)