Re:Avoiding the Adjective Fallacy
by vinceguidry on Wednesday September 30, 2015 @11:16AM
(#10304576)
I think there's a subtlety you might be missing, correct me if I'm wrong.
I stated in my first reply that the growth rate is notated as a function of the size of the input. Big O is itself an approximation, you don't use it if you absolutely have to know all the other factors that don't vary on the size of the input. Such as if they vary on your memory architecture. In practice they tend not to matter, Big-O is sufficient for most purposes.
If you do need the detail, you remove the Big-O and write out your other factors so you can compare them to other algorithms at the right level of detail. There are also other notations you can use that convey other concepts, such as little-o, little-theta, big-theta. When you use a Landau symbol[1], as these are called, you're making an approximate statement by definition.
It's still perfectly fine to call array access O(1), even if your data is stored on Pluto, and it's Odysseus doing a space opera Odyssey for each retrieval, you're still only going there twice. Even if there are sub-algorithms that you are calling within the main one, you're still only calling them a constant number of times. If the first time you go to Pluto to get data it takes 6 months and the second time it takes 30 years, because of complications, it's still constant time.
If you were accessing a linked list stored on Pluto, then you're going to Pluto a number of times depending on how deep in the linked list your data is, assuming it's a dumb probe and it can't figure out where to go once it gets to Pluto and has to come back to earth to figure out what to do next. (go back to Pluto)
If it turns out retrieval time matters, or other factors besides the size of the input, then you can't approximate over them and Big-O ceases to be useful.
I stated in my first reply that the growth rate is notated as a function of the size of the input. Big O is itself an approximation, you don't use it if you absolutely have to know all the other factors that don't vary on the size of the input. Such as if they vary on your memory architecture. In practice they tend not to matter, Big-O is sufficient for most purposes.
If you do need the detail, you remove the Big-O and write out your other factors so you can compare them to other algorithms at the right level of detail. There are also other notations you can use that convey other concepts, such as little-o, little-theta, big-theta. When you use a Landau symbol[1], as these are called, you're making an approximate statement by definition.
It's still perfectly fine to call array access O(1), even if your data is stored on Pluto, and it's Odysseus doing a space opera Odyssey for each retrieval, you're still only going there twice. Even if there are sub-algorithms that you are calling within the main one, you're still only calling them a constant number of times. If the first time you go to Pluto to get data it takes 6 months and the second time it takes 30 years, because of complications, it's still constant time.
If you were accessing a linked list stored on Pluto, then you're going to Pluto a number of times depending on how deep in the linked list your data is, assuming it's a dumb probe and it can't figure out where to go once it gets to Pluto and has to come back to earth to figure out what to do next. (go back to Pluto)
If it turns out retrieval time matters, or other factors besides the size of the input, then you can't approximate over them and Big-O ceases to be useful.
[1] http://mathworld.wolfram.com/LandauSymbols.html