Geek Answers Handbook

The complexity of the input algorithm is fixed

I found some links about the big O notation, but as I understand it, the complexity of the algorithm is a function of the size of the input.

For example, if the complexity of sorting bubbles is O(n^2) , n is the size of the input array. Correctly?

But how can I determine the complexity of an algorithm that has a fixed input size and depends on the input values. For example, a search for the Greatest Common Divisor (GCD) would look like this:

 def GCD(x, y): while x != y: if x < y: x, y = y - x, x else: x, y = x - y, x return x

What is the complexity of this algorithm? And how is this determined?

Edit: The name of the function and the corrected name of the algorithm are changed. ShreevatsaR, thanks for pointing this out.

+6
algorithm big-o
source share
4 answers

People play a little fast and freely with a big O recording. In the case of GCD, they usually do this in two ways:

1) You are right, the algorithmic complexity, and therefore the Big-O designation, should be indicated in terms of size in input bits, and not in terms of input values. How P, NP, etc. are defined. Taking a binary input and randomly large numbers (e.g., BigNum representation), and N the number of input bits, your GCD requires no more than 2 ^ N subtractions, each of which takes O (N) time, to complete each digit, the numbers are subtracted. So, O (N * 2 ^ N). Of course, a GCD can be made much faster if you use division rather than subtraction: O (N ^ 2).

Thus, when we say that testing was confirmed in polynomial time in 2002 , this is a technical definition of complexity, and we are the average polynomial in the number of digits (which is the difficult part), and not polynomial in the input number itself (which is trivially easy to do in “sublinear time” using trial division).

But in practice, for algorithms that take a fixed number of integer inputs, it is more convenient to talk about complexity, as if N were the input itself, and not the size of the input. This is not harmful if you understand what you mean in cases that may be ambiguous.

2) In practice, whole inputs are often fixed, 32-bit or any, and operations with them, such as addition, multiplication and division, are O (1) time. We use these facts selectively in our analysis of order. Technically, if your GCD program accepts input data up to (2 ^ 32-1), then this is O (1). He has a fixed upper bound on the time of his work. The end of the analysis.

Although technically correct, this is not a very useful analysis. Almost everything you do on a real computer is O (1) on the same basis that the size of the problem is limited by hardware.

It is usually more convenient to assume that adding O (1), because the numbers are fixed in size, but ignore that the GCD is also O (1), it is pretending that its behavior in the range [1, 2 ^ 32) continues to infinity, and analyze this on this basis. Then, with N maximum value of the two inputs, O (N) is output: O (N) subtractions, each of which takes a constant time.

Again, this is not ambiguous if you know what the conditions of the link are, but beware of incorrect comparison of the first analysis that I gave the Euclidean division algorithm, O (N ^ 2), against this analysis of the subtraction algorithm, O (N). N is not the same in everyone, and subtraction is not faster; -)

+11
source share

The Big-O designation should indicate what is being measured.

For example, Big-O notation for sorting algorithms usually measures the number of comparisons.

Your GCD example can be measured by comparing the x and y values ​​with the number of instructions executed. Let's take a closer look:

 def GCD(x, y): while x != y: # 1 if x < y: # 2 x, y = y - x, x # 3 else: # 4 x, y = x - y, x # 5 return x # 6

Work from the inside out.

Regardless of the x and y values, steps 3 and 5 will always take one instruction. Therefore, the if in step 2 will always execute two instructions.

A more complicated question is step 1. With each iteration, either x or y will be reduced by a smaller value. Suppose x > y . There will be one of two things:

  • If it started with x % y == 0 , then the loop will be executed (x / y) - 1 time, and the program will stop.

  • Otherwise, x will be reduced (x / y) times before it becomes smaller than y , and the program will continue to work.

You can easily measure the number of instructions for any given x and y . You can easily show that for a given number z you do not need more than z - 1 subtractions - or 2 * (z-1) instructions. (Think of gcd(z, 1) .)

+2
source share

input size is the sum of the sizes of the numbers x and y (for example, how many digits are indicated in the number)

+1
source share

The greater complexity of O is the worst behavior in asymptotic operation. This does not necessarily depend on the size of the input (the number of inputs) to a particular algorithm, although this is often the case. In other words, it is a limit function describing the runtime when inputs are accepted ad infinitum.

In your case, if x or y are unbounded, then the asymptotic runtime is also. If not, think about runtime if x = 1 and y = Int32.Max?

+1
source share

More articles:


All Articles