CODEWITHSUNDEEP
time-complexityturing-machines
chris765
chris765

Reputation: 1

operations on turing machine

Consider the problem: List := {< A, c> | A is a list of integers that contains a,b such that a + b = c} where the length of A is n. The algorithm we use to show that this problem is in class P adds two integers say A[i]+A[j] from A and check if it is equal to c or not. why can this test can be done in O(1)rounds? Thank you in advance.

Upvotes: 0

Views: 623

Answers (1)

trincot
trincot

Reputation: 350310

There are two approaches when speaking of computational complexity:

  • The involved integers are considered to be single words, i.e. they have a fixed range that typically fits in one CPU register. This could for instance be a signed 64-bit integer.

  • The involved integers are considered to be unbounded: the memory to hold them will vary. Unless algorithms really work with so-called "big integers", this is a more theoretical approach.

We see the first approach in Wikipedia's article on Time complexity. For instance, for linear time it gives this example:

For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.

The second approach is taken in Wikipedia's article on computational complexity of mathematical operations. For instance, for addition it has:

Operation Input Output Algorithm Complexity
Addition Two 𝑛-digit numbers, 𝑁 and 𝑁 One 𝑛+1-digit number Schoolbook addition with carry Θ(𝑛), Θ(log(𝑁))

For the algorithm in question

I'll assume that the list members are signed integers.

Both the addition and comparison of two integers has O(1) time complexity according to the first approach, and so the overall time complexity is O(𝑛²).

According to the second approach both addition and comparison are O(log(max(abs(𝐴𝑖))). We could also involve 𝑐 here: but even if it has a greater absolute value than all the sums of pairs, we can do the comparison with a time complexity of max(abs(𝐴𝑖))). And so the overall time complexity is O(log(max(abs(𝐴𝑖)))𝑛²).

Upvotes: 1

Related Questions