6

Related to exponential in terms of? (nonetheless different from it):

Assume that you have an algorithm (producing gizmos) whose inputs are three numbers t, d, and h, which are interpreted by a human as the number of thingums, doodahs, and hickeys. Suppose the running time of the algorithm is the function g, which depends on t, d, and h. Further, let g(t,d,h) ≤ dᶜ, where c is some expression exceeding 1 and depending on t and h, but not on d.

I would like to use plain English to express this fact (e.g., in an abstract) in a simplified way. Do we write

The algorithm runs in polynomial time in the number of doodahs.

or

The algorithm runs in polynomial time with the number of doodahs.

?

My English teacher corrected it to

The algorithm runs in polynomial time in terms of the number of doodahs.

I think this cannot be quite right.

Which version is correct? And how about

The algorithm runs in worst-case polynomial time in/with the number of doodahs.

Any better version?

I welcome answers from mathematicians who are native AmE speakers and have an excellent command of English.

|improve this question
  • 1
    You might find a more targeted audience in math.stackexchange.com – Davo Mar 24 '17 at 16:20
  • I understand. :) – Davo Mar 24 '17 at 16:28
  • @LeonMeier This is out of my expertise, so this is a genuine question, not an answer, but wouldn't polynomial time be if g(t,d,h) ≤ dᶜ where c is a constant? Your time function doesn't appear to be bounded by a polynomial with a constant degree - since C is a function of other inputs to the algorithm. Or is the function c(t, h) bounded by a constant above? – Adam Jun 23 '17 at 23:08
  • Got it. In that case I would say it runs in polynomial time with respect to the number of doodahs (and in exponential time with respect to the number of things and hoosiewhatsits). That's a very common construction when describing mathematical functions:(Eg The value of a continuously compounded investment varies linearly with respect to present value and exponentially with respect to time.) – Adam Jun 24 '17 at 20:36
3

Well, "polynomial time" is already jargon so you're out of the realm of "standard" English. Unless there was a good reason not to, I would be explicit and use the actual math to describe exactly what the polynomial looks like and what factors into the equation. Example from the Wikipedia article on Time complexity:

The Euclidean algorithm for computing the greatest common divisor of two integers is one example. Given two integers a and b the running time of the algorithm is bounded by O((log a + log b)2) Turing machine steps. This is polynomial in the size of a binary representation of a and b as the size of such a representation is roughly log a + log b.

If it's not necessary to be explicit, you can just say "the algorithm runs in polynomial time". Otherwise there is probably a lot of leeway in how you phrase it, since statements like this rely more on the math than English grammar.

The algorithm runs in polynomial time (based on)/(relative to)/(varying with) the number of doodahs

|improve this answer
  • I wouldn't have had a clue what polynomial time meant until a few months ago, but I hear it a lot since I've started watching Youtube talks by computer scientists and mathematicians. And so far as I can recall, it's never explicitly qualified by anything like with respect to [something] - the context is always one where they're talking about an algorithm that either solves or approximates some equation containing one or more exponential terms (where without that clever new approach the time required would be expected to rise exponentially with those variables). – FumbleFingers Mar 24 '17 at 19:30
  • @FumbleFingers the algorithm runs in polynomial time, but the polynomial itself is an equation that takes a certain number of variables. I'm not sure how to summarize, in a word, the relationship between the equation and its variables. – Andrew Mar 24 '17 at 20:29
0

This might be an idiomatic contraction of "in the domain of the numbers of doodahs". The polynomial is a function in the domain. Otherwise the preposition doesn't make much sense and I'd prefer "to run over/through the numbers".

|improve this answer
  • "The function runs in polynomial time in the domain of the number of Xs." I might be wrong (but downvoters didn't comment why). Given that the function is a relation of the time t over the values X, I'd still tend to use over. but in is shorter so if you are writing, that might save some space at least. – Hector von Mar 25 '17 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy