• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Square root complexity?

 
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.

 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ?
 
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Bartender
    Posts: 5465
    212
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • 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: 954
    4
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • 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: 79178
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • 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.
     
    Rancher
    Posts: 1044
    6
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • 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: 79178
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • 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: 1044
    6
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    AKS primality test
     
    Come have lunch with me Arthur. Adventure will follow. This tiny ad:
    a bit of art, as a gift, that will fit in a stocking
    https://gardener-gift.com
    reply
      Bookmark Topic Watch Topic
    • New Topic