--%>
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 : What is limit x tends to 0 log(1+x)/x

    What is limit x tends to 0  log(1+x)/x to the base a?

  • Q : Explain the work and model proposed by

    Explain the work and model proposed by Richardson.

    		•
  • Q : Define Big-O notation Big-O notation :

    Big-O notation: If f(n) and g(n) are functions of a natural number n, we write f(n) is O(g(n)) and we say f is big-O of g if there is a constant C (independent of n) such that f

    		•
  • Q : Graph Theory is the n-Dimensional Qn

    is the n-Dimensional Qn Hamiltonian? Prove tour answer

    		•
  • Q : What is Big-O hierarchy The big-O

    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<

    		•
  • Q : Mean and standard deviation of the data

    Below is the amount of rainfall (in cm) every month for the last 3 years in a particular location: 130 172 142 150 144 117 165 182 104 120 190 99 170 205 110 80 196 127 120 175

    		•
  • Q : Examples of groups Examples of groups:

    Examples of groups: We now start to survey a wide range of examples of groups (labelled by (A), (B), (C), . . . ). Most of these come from number theory. In all cases, the group axioms should be checked. This is easy for almost all of the examples, an

    		•
  • 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 : Global And Regional Economic Development

    The Pharmatec Group, a supplier of pharmaceutical equipment, systems and services, has its head office in London and primary production facilities in the US. The company also has a successful subsidiary in South Africa, which was established in 1990. Pharmatec South A

    		•
  • 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

    		•