• Post Reply Bookmark Topic Watch Topic
  • New Topic

Square root complexity?  RSS feed

 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All, i am working on an assignment given by my professor where i have to give the solution in square root complexity but i am unable to understand how to get it? I looked on the google but din't understand.

Could any one please give me an example and explain how to get square root complexity?
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What that means is: when the algorithm has to deal with N items, it should take a number of operations that is proportional to the square root of N.

To achieve this, you'll have to choose the appropriate algorithm.

 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Tushar,

an example would be to determine if N is a prime number.
One algorithm would be: try the numbers 1... sqrt(N),
to see if one of 'm evenly divides N.

Greetz,
Piet
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Jasper.. You mean like if i have numbers 0 to 100 and square root of 100 is 10 then i have to find numbers having space 10. ex: 0, 10, 20, 30,... 100?

Thanks Piet.. Are you referring the same condition as i mentioned above?

Could you please guys share some link or example where i can see the implementation ?
 
Campbell Ritchie
Marshal
Posts: 56553
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Surely that is the Sieve of Eratosthenes.

No, for 100 you would test up to √100 using 2, 3, 4, 5, 6, 7, 8, 9, 10.
It says in the Curious Incident of the Dog in the Night‑Time that the number of prime numbers up to a certain number n is approximately proportional to logn. If you already have a source of prime numbers in order, then you would need to check up to ilog(√n) numbers (i being an unspecified integer). But log(√n) = ½log(n), so that reduces to logarithmic complexity.
In Abelson and Sussman it mentions a simpler method of finding whether a number is prime which runs in constant time but may miss out some values. So,
  • 1: Populating a sieve runs in nlogn time.
  • 2: Using a ready‑made sieve to find whether a number is prime runs in logarithmic time.
  • 3: Testing for primeness without a sieve runs in √n time at worst. Somebody may be able to show it is quicker. Since most factors are small (2, 3, 5 etc) it may actually run in logarithmic time. Not sure, however.
  •  
    Piet Souris
    Master Rancher
    Posts: 2044
    75
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:Surely that is the Sieve of Eratosthenes. (...)

    ?
    I gave OP an example of something that looks like O(sqrt(n)). That's what OP asked for.
    Now, indeed I'm not sure if my example is indeed a sqrt(n), but it's just an example.
    What the sieve of Eratosthenes has to do with that is beyond me.
     
    Tushar Goel
    Ranch Hand
    Posts: 934
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell, I am still trying to understand what you said. They still floating over my head.

    I think you are referring to this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
     
    Campbell Ritchie
    Marshal
    Posts: 56553
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Piet Souris wrote: . . .
    I gave OP an example of something that looks like O(sqrt(n)). . . .
    Yes, you did. And when I wrote it down I realised that most non‑prime numbers would be caught early in the process, so started to doubt myself whether it is actually √n time.
     
    Ivan Jozsef Balazs
    Rancher
    Posts: 999
    5
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:

    It says in the Curious Incident of the Dog in the Night‑Time that the number of prime numbers up to a certain number n is approximately proportional to logn.



    It has not that fancy title but it says here:

    Prime number theorem

    that

    The first such distribution found is π(N) ~ N / ln(N), where π(N) is the prime-counting function and ln(N) is the natural logarithm of N.


    and here Prime-counting function

    that

    In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x




     
    Campbell Ritchie
    Marshal
    Posts: 56553
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Actually I think the previous poster was right: if you don't have a Sieve and wish to confirm that a number is prime, it probably runs in O√n complexity.
     
    Ivan Jozsef Balazs
    Rancher
    Posts: 999
    5
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    AKS primality test
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!