M.Mahdi's blog

Why it's O(nlogn)?
By M.Mahdi, 9 years ago, In English

Hi!
Did you know is O(nlogn)? (ω(n) is the number of distinct prime divisors of n)

I wonder why! Do you have any mathematical proof for this?

  • Vote: I like it
  • +80
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +336 Vote: I do not like it

Because 2w(i) ≤ d(i) (d(n) is the number of divisors of n), so this is less than sum of d(i), which is the number of pairs i, j such that j divides i, which is sum of n/j, which is O(nlogn).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +100 Vote: I do not like it

    At the first look I was totally surprised about this fact, but it sounds easy when you say it like that!
    Thanks!

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      it's nice information, do you know any problems that can be solved using it?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +19 Vote: I do not like it

        It's one of training tasks for our national OI (INOI):
        Consider a n × n forest. For each relatively prime pair (i, j)i, j ≤ n, we plant a tree on position (i, j). The problem is to calculate total sum of pairwise distances between trees!
        n ≤ 106, distance((a, b), (c, d)) = |a - c| + |b - d|

        Also you can use that fact for this problem.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          I don't think that much theoretically about problem, since each number lower than 10^6 has at most 7 distinct prime divisor, we can perform 2^7 * 10^6 :D This problem is much like SGU 370

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +24 Vote: I do not like it

            Yes, but it's always good to know the exact complexity of our solution! (Without considering the limits)

            → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

What about lower bound? I can prove just Ω(nloglogn)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +71 Vote: I do not like it

Lower bound:

Let Pn be a set of primes not larger than n.

(look here: http://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes). It follows that average number of different primes divisors is , so since 2x is convex we get that it's at least .

→ Reply