--%>
Assignment Help - homework help

What is Big-O hierarchy

The big-O hierarchy: A few basic facts about the big-O behaviour of some familiar functions are very important. Let p(n) be a polynomial in n (of any degree). Then

logbn is O(p(n)) and p(n) is O(an);

for any base b and any a. In words: logs are big-O of polynomials and polynomials are big-O of exponentials.

Note that since logbn = logcn/ logcb, we have

logbn is O(logcn);

for any fixed b and c, since logcb is a constant.

   Related Questions in Mathematics

  • Q : Row-echelon matrix Determine into which

    Determine into which of the following 3 kinds (A), (B) and (C) the matrices (a) to (e) beneath can be categorized:       Type (A): The matrix is in both reduced row-echelon form and row-echelon form. Type (B): The matrix

    		•
  • Q : Ordinary Differential Equation or ODE

    What is an Ordinary Differential Equation (ODE)?

    		•
  • Q : Define Well-formed formulas or Wffs

    Wffs (Well-formed formulas): These are defined inductively by the following clauses:    (i) If  P  is an n-ary predicate and  t1, …, tn are terms, then P(t1, …, t

    		•
  • Q : Problem on Prime theory Suppose that p

    Suppose that p and q are different primes and n = pq. (i) Express p + q in terms of Ø(n) and n. (ii) Express p - q in terms of p + q and n. (iii) Expl

    		•
  • Q : Explain Factorisation by Fermats method

    Factorisation by Fermat's method: This method, dating from 1643, depends on a simple and standard algebraic identity. Fermat's observation is that if we wish to nd two factors of n, it is enough if we can express n as the di fference of two squares.

    		•
  • Q : Probability assignments 1. Smith keeps

    1. Smith keeps track of poor work. Often on afternoon it is 5%. If he checks 300 of 7500 instruments what is probability he will find less than 20substandard? 2. Realtors estimate that 23% of homes purchased in 2004 were considered investment properties. If a sample of 800 homes sold in 2

    		•
  • Q : Econ For every value of real GDP,

    For every value of real GDP, actual investment equals

    		•
  • Q : Simulation with Arena An office of

    An office of state license bureau has two types of arrivals. Individuals interested in purchasing new plates are characterized to have inter-arrival times distributed as EXPO(6.8) and service times as TRIA(808, 13.7, 15.2); all times are in minutes. Individuals who want to renew or apply for a new d

    		•
  • Q : Who independently developed

    Who independently developed a model for simply pricing risky assets?

    		•
  • Q : Linear programming model of a Cabinet

    A cabinet company produces cabinets used in mobile and motor homes. Cabinets produced for motor homes are smaller and made from less expensive materials than those for mobile homes. The home office in Dayton Ohio has just distributed to its individual manufacturing ce

    		•