3 ms·

I'm confused by this. His function f(x) is of linear time-complexity (with respect to the value of x). Assume it takes time c1 to print a number, this I will

I'm confused by this. His function f(x) is of linear time-complexity (with respect to the value of x). Assume it takes time c1 to print a number, this I will create a function g(x) = c1*x + k, where k is a constant representing the overhead. Then f(x) < g(x) and g(x) element of the set O(x). I am not sure how that makes his function run in exponential time. Am I misunderstanding something?

eieio 13y ago
The function runs in linear time relative to the value of x. However, time complexity refers to the size of the input, not the value. For example, binary search's O(log n) time complexity refers to the number of elements n in a list(n varies with the list's size). x + 1 will always increase the value of x, but not necessarily the size. The size of x is the number of digits in x. f(x) runs once if x=1, ten times if x=10, one hundred times if x=100, etc. So each time x's size increases by 1, f's runtime increases by a factor of 10. It's a very literal definition of time complexity and it's counterintuitive, but ultimately it does make sense.
- deleted 13y ago
  [deleted]
  - eieio 13y ago
    It's the difference between a function taking a list and a function taking a number. A list's size depends on the number of elements in the list. Adding an element to a list increases the size of the list. A number's size depends on the number of digits required to express the number. Number++ will always increase the numbers value, but not necessarily the number's size. anonymouz's point is that we should describe f(x)'s runtime in terms of the size of x, not the value of x. While I agree that the natural interpretation is to use x's value when x is a number, and x's size is going to be fixed anyway, f(x) is exponential in relation to x's size and linear in relation to x's value. Put another way: 4 and 5 have different values, but the same size: we're expressing both with 1 digit. 4 and 10 have different values and different sizes, as we require 2 digits to express 10 and only 1 to express 4. Of course we'd probably be dealing with binary, but it's the same idea. It's really a question of semantics/how you interpret OP's example and the natural interpretation leads to the function being O(n). However anonymouz makes an interesting point that I hadn't considered before.
    - hermannj314 13y ago
      Sorry, I deleted my post before I saw your response.
    - millstone 13y ago
      Consider a function that prints a list of the numbers 1 through N. This function is linear in the size of its input, because we're talking about the size of a list. But now, make a function that prints the first N numbers. This function is exponential in the size of its input, because we're talking about the size of a number. We can optimize this second function by replacing our binary representation of a number with a unary ("tallying") representation. Now the size of a number grows linearly with its value, and so our function is linear instead of exponential. Nice win!
      - eieio 13y ago
        anonymouz's interpretation is bizarre and definitely not how I'd think about the function, I'm just trying to explain where he's coming from. I don't plan on using the interpretation in the future but it was confusing to me too and I thought it was an interesting thought so I figured I'd attempt to explain.
        anonymouz 13y ago
        > anonymouz's interpretation is bizarre and definitely not how I'd think about the function. It is usually understood that one measures the time complexity of an algorithm in the size of the input (only if the input is an integer, would it even make sense to measure it in the value of the input). So you may of course use whatever definition you like, but be careful that statements about the time complexity of certain things are often made without referring to the exact definitions used, and you may then misunderstand them. For example, when people say "We don't know a polynomial-time algorithm to factor integers" they mean polynomial time in the size of the input (i.e., number of digits/bits of the integer). The problem would trivially be polynomial time if you allowed it to be polynomial in the integer itself.
    - ShellfishMeme 13y ago

eieio 13y ago

The function runs in linear time relative to the value of x. However, time complexity refers to the size of the input, not the value. For example, binary search's O(log n) time complexity refers to the number of elements n in a list(n varies with the list's size). x + 1 will always increase the value of x, but not necessarily the size. The size of x is the number of digits in x. f(x) runs once if x=1, ten times if x=10, one hundred times if x=100, etc. So each time x's size increases by 1, f's runtime increases by a factor of 10. It's a very literal definition of time complexity and it's counterintuitive, but ultimately it does make sense.

deleted 13y ago
[deleted]
- eieio 13y ago
  It's the difference between a function taking a list and a function taking a number. A list's size depends on the number of elements in the list. Adding an element to a list increases the size of the list. A number's size depends on the number of digits required to express the number. Number++ will always increase the numbers value, but not necessarily the number's size. anonymouz's point is that we should describe f(x)'s runtime in terms of the size of x, not the value of x. While I agree that the natural interpretation is to use x's value when x is a number, and x's size is going to be fixed anyway, f(x) is exponential in relation to x's size and linear in relation to x's value. Put another way: 4 and 5 have different values, but the same size: we're expressing both with 1 digit. 4 and 10 have different values and different sizes, as we require 2 digits to express 10 and only 1 to express 4. Of course we'd probably be dealing with binary, but it's the same idea. It's really a question of semantics/how you interpret OP's example and the natural interpretation leads to the function being O(n). However anonymouz makes an interesting point that I hadn't considered before.
  - hermannj314 13y ago
    Sorry, I deleted my post before I saw your response.
  - millstone 13y ago
    Consider a function that prints a list of the numbers 1 through N. This function is linear in the size of its input, because we're talking about the size of a list. But now, make a function that prints the first N numbers. This function is exponential in the size of its input, because we're talking about the size of a number. We can optimize this second function by replacing our binary representation of a number with a unary ("tallying") representation. Now the size of a number grows linearly with its value, and so our function is linear instead of exponential. Nice win!
    - eieio 13y ago
      anonymouz's interpretation is bizarre and definitely not how I'd think about the function, I'm just trying to explain where he's coming from. I don't plan on using the interpretation in the future but it was confusing to me too and I thought it was an interesting thought so I figured I'd attempt to explain.
      - anonymouz 13y ago
        > anonymouz's interpretation is bizarre and definitely not how I'd think about the function. It is usually understood that one measures the time complexity of an algorithm in the size of the input (only if the input is an integer, would it even make sense to measure it in the value of the input). So you may of course use whatever definition you like, but be careful that statements about the time complexity of certain things are often made without referring to the exact definitions used, and you may then misunderstand them. For example, when people say "We don't know a polynomial-time algorithm to factor integers" they mean polynomial time in the size of the input (i.e., number of digits/bits of the integer). The problem would trivially be polynomial time if you allowed it to be polynomial in the integer itself.
  - ShellfishMeme 13y ago