--%>
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 : Who independently developed

    Who independently developed a model for simply pricing risky assets?

    		•
  • Q : Set Theory & Model of a Boolean Algebra

    II. Prove that Set Theory is a Model of a Boolean Algebra The three Boolean operations of Set Theory are the three set operations of union (U), intersection (upside down U), and complement ~.  Addition is set

    		•
  • 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 : Mathematical and Theoretical Biology

    Mathematical and theoretical biology is an interdisciplinary scientific research field with a range of applications in the fields of biology, biotechnology, and medicine. The field may be referred to as mathematical biology or biomathematics to stress the mathematical

    		•
  • 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 : What is Non-Logical Vocabulary

    Non-Logical Vocabulary: 1. Predicates, called also relation symbols, each with its associated arity. For our needs, we may assume that the number of predicates is finite. But this is not essential. We can have an infinite list of predicates, P

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

    is the n-Dimensional Qn Hamiltonian? Prove tour answer

    		•
  • 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 : How to calculate area of pyramid

    Calculate area of pyramid, prove equation?

    		•
  • Q : Maths A cricketer cn throw a ball to a

    A cricketer cn throw a ball to a max horizontl distnce of 100m. If he throws d same ball vertically upwards then the max height upto which he can throw is????

    		•