Polynomial equations : Algorithms

Question

I have been reading through material about algorithms (in Java).

This question asks what which of the polynomial expressions is correct.

I need further material to understand how to classify each of the expressions

as correct or not correct.

Answer 1

So, I cannot read Greek or whatever language that is, but I think I can make out enough of what is being asked to help answer:

a.   (n^4 - 35n^2logn)        // initial expression
   = O(n^4)                   // 35n^2logn is always positive, so we can
                              // drop this subtracted term if it helps us get
                              // to the O class we want
   = O(n^5)                   // n^4 grows more slowly than n^5
   this is true

b.   log_3(n^8)
   = 8log_3(n)                // law of logs, log(x^y) = ylog(x)
   = 8log_8(n)/log_8(3)       // law of logs, log_a(x) = log_b(x)/log_b(a)
   = (8/log_8(3))log_8(n)     // rearrange expression so constants are together
   = O(log_8(n))              // drop the constants
   this is true

c. n^2 + n
   this is false; polynomials grow faster than any power of logs

d. 100n^8 + 78n^7 + 30n^5sqrt(n) + n^2 + n
   = O(n^8)                                  // drop all but the high-order term
   = O(2^n)                                  // exponentials grow faster than polynomials if the base is greater than one
     this is true

e. 2^n
   this is false; exponentials grow faster than polynomials if the base is greater than one

f. f(1) = 1, f(n) = f(n-1) + n
   <=>
   f(n) = n(n+1)/2
        = (1/2)n^2 + (1/2)n
        this is false; the high-order term is n^2 which grows faster than n

If there are questions about proving any of these specifically, please let me know and I can update the answer. Otherwise, you can use these as starting points to write your own proofs.