programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Square root complexity?

Tushar Goel
Ranch Hand
Posts: 934
4
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
• 1
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
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
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
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
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
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
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
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
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
AKS primality test