--%>
Assignment Help - homework help

State Measuring complexity

Measuring complexity: Many algorithms have an integer n, or two integers m and n, as input - e.g., addition, multiplication, exponentiation, factorisation and primality testing. When we want to describe or analyse the `easiness' or `hardness' of the algorithm, we want to measure its `running time' as a function of the `size' of the input value(s).

If the input value is n, then it is usual to use the number of (decimal) digits, or bits (binary digits), required to store n as a measure of the size of n.

Given input n, the number of decimal digits in n is given by

[log10 n] +1;

where [x], pronounced `floor of x', denotes the greatest integer less than or equal to x. The number of binary digits or bits is similarly given by

[lg n] +1;

where we use the abbreviation lg x for log2 x (this notation is common, but not completely standard).

   Related Questions in Mathematics

  • Q : Law of iterated expectations for

     Prove the law of iterated expectations for continuous random variables. 2. Prove that the bounds in Chebyshev's theorem cannot be improved upon. I.e., provide a distribution that satisfies the bounds exactly for k ≥1, show that it satisfies the bounds exactly, and draw its PDF. T

    		•
  • Q : First-order formulas over the

    Consider the unary relational symbols P and L, and the binary relational symbol On, where P(a) and I(a) encode that a is apoint and a (sraight) line in the 2-dimensional space, respectively, while On(a,b) encodes  that a is a point, b is a line, and o lies on b.

    		•
  • Q : Profit-loss based problems A leather

    A leather wholesaler supplies leather to shoe companies. The manufacturing quantity requirements of leather differ depending upon the amount of leather ordered by the shoe companies to him. Due to the volatility in orders, he is unable to precisely predict what will b

    		•
  • Q : What is the definition of a group Group

    Group: Let G be a set. When we say that o is a binary operation on G, we mean that o is a function from GxG into G. Informally, o takes pairs of elements of G as input and produces single elements of G as output. Examples are the operations + and x of

    		•
  • Q : Formulating linear program of an oil

    An oil company blends two input streams of crude oil products alkylate and catalytic cracked to meet demand for weekly contracts for regular (12,000 barrels) mind grade ( 7,500) and premium ( 4,500 barrels) gasoline’s . each week they can purchase up to 15, 000

    		•
  • Q : State Prime number theorem Prime number

    Prime number theorem: A big deal is known about the distribution of prime numbers and of the prime factors of a typical number. Most of the mathematics, although, is deep: while the results are often not too hard to state, the proofs are often diffic

    		•
  • Q : Pig Game Using the PairOfDice class

    Using the PairOfDice class design and implement a class to play a game called Pig. In this game the user competes against the computer. On each turn the player rolls a pair of dice and adds up his or her points. Whoever reaches 100 points first, wins. If a player rolls a 1, he or she loses all point

    		•
  • Q : Explain Black–Scholes model Explain

    Explain Black–Scholes model.

    		•
  • Q : Where would we be without stochastic

    Where would we be without stochastic or Ito^ calculus?

    		•
  • Q : Solve each equation by factoring A

    A college student invested part of a $25,000 inheritance at 7% interest and the rest at 6%.  If his annual interest is $1,670 how much did he invest at 6%?  If I told you the answer is $8,000, in your own words, using complete sentences, explain how you

    		•