Note about Sipser's use of big O notation when talking about padding
Author Message
t8wehrro Offline
TA


Reputation: 0
Post: #1
Note about Sipser's use of big O notation when talking about padding
The following sentence is from the argument on page 364 of Sipser Edition 2 (solution to 9.15):

"The language pad(A, n²) ∈ SPACE(n) because you have enough space to run the O(n²) algorithm for A, using space that is linear in the padded language."

Sipser is using confusing style here, in my opinion, but it's still a correct use of the language/notation. The terms "pad(A, n²)", "SPACE(n)", and "O(n²)" all temporarily introduce a new variable, "n", whose scope ends at the next ")". The way I would write it is with the second occurrence of "n" replaced by "m". But what Sipser wrote means exactly the same thing. Moreover, both are equivalent to the following confusing version (at least, provided "k" and "m" are not already being used for something else): "The language pad(A, n²) ∈ SPACE(k) because you have enough space to run the O(m²) algorithm for A, using space that is linear in the padded language."

Thanks to Christian for bringing this up.
2012-12-01 19:17
Find all posts by this user Quote this message in a reply
Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5


Forum Jump:


User(s) browsing this thread: 1 Guest(s)