Oh works with Summations?

 

I know this isn't strictly a programming question, but it is a computer science question so I'm hoping someone can help me.

I've been working on my Algorithms homework and figuring out the Big-Oh, Big-Omega, Theta, etc, of several algorithms. I'm proving them by finding their C and N0 values and all is going well.

However, I've come across my last two problems in the set and I'm struggling figuring out how to do them (and google isn't helping much).

I haven't had to figure out the Big-Oh/Omega of summations before.

My last two problems are:

  • Show that Σ (i=1 to n) of i2 is O(N3)

    • and

  • Show that Σ (i=1 to n) of [log2i] is Ω(n log n)

    • My question is, How do I show that?

    For example, in the first one, intuitively I can't see how that summation of i2 is O(N3). The second one confuses me even more. Can someone explain how to show the Big-Oh and and Big-Omega of these summations?

    My guess is that what the question statement means is if you're summing the results of some calculation for which the running time is proportional to i2 in the first case, and proportional to log2i in the second case. In both cases, the running time of the overall summation is "dominated" by the larger values of N within the summation, and thus the overall big-O evaluation of both will be N*O(f) where f is the function you're summing.

    http://en.wikipedia.org/wiki/Big_O_notation

    N repetitions of g(m)=O(f(m)) is O(N*f(m)) for any f(N).

    Sum of i=1..N of i*g(i) is O(N*f(N)) if g(n)=O(f(n)) and f is monotonic.

    Definition: g(n)=O(f(n)) if some c,m exist so for all n>m, g(n)<=c*f(n)

    The sum is for i=1..N of i*f(i) .

    If f is monotonic in i this means every term is <= if(N) <= Nf(N). So the sum is less than N*c*f(N) so the sum is O(N*f(N)) (witnessed by the same c,m that makes g(n)=O(f(n)))

    Of course, log_2(x) and x^2 are both monotonic.

  • Σ (i=1 to n) i2 = n(n+1)(2n+1)/6, which is O(n3).

  • Note that (n!)2 = (1 n) (2(n-1)) (3(n-2))...((n-1)2) (n 1)
    = Π (i=1 to n) i (n+1-i)
    >= Π (i=1 to n) n
    [Eg, because for each i=1 to n, (i-1)(ni) >= 0. Compare with Graham/Knuth/Patashnik, section 4.4]
    = nn.
    Thus, n! >= nn/2, and therefore
    Σ (i=1 to n) log i = log Π (i=1 to n) i = log n! >= log nn/2 = (n/2) log n, which is Ω(n log n).

    • 链接地址: http://www.djcxy.com/p/43104.html

    上一篇: SVN忽略子树中的所有文件（不是文件夹）

    下一篇: 哦，与Summations合作？