5 ms·

def print_first_item(items): print items[0] This function runs in O(1) time (or "constant time") relative to its input. If this were C where the

def print_first_item(items): print items[0] This function runs in O(1) time (or "constant time") relative to its input. If this were C where the only types are fixed-size, that might be true. But in Python it seems like items[0] could display as 10 gigabytes of JSON. And if stdout is piped to a process that isn't consuming its input, it might never terminate naturally. Also, since Python has arbitrarily large integers, an expression like "index += 1" probably runs in O(log(index)) time, not O(1) time.

dpzmick 7y ago
in C, it items[0] could segfault, the fault could be caught by a signal handler which does some unbounded amount of work, then populates the appropriate memory location and returns... More realistically, the page of memory that items[0] is sitting on could be swapped to disk, requiring the OS to do some big operation. trying to write a piece of code with the big-O you are looking for generally has a huge number of caveats. I'm undecided on whether this is a feature (abstraction) or a flaw (easily misleading)
- xthestreams 7y ago
  I think you (and others) are misunderstanding the purpose of the big-O notation. It is used to discuss about algorithms, not about their implementation.
- GuB-42 7y ago
  And "print items[0]" is actually O(n) where n is the size of the string. Maybe even O(n^2) if the item is a big number and a binary to decimal conversion is required. But it is doesn't matter here because we have chosen n to be the size of the array, because it is what we are studying. Here it is big-O "constant time" because the execution time doesn't depend on on the size of the array, assuming it is really big. Not that every call of the function will take the same time to run. The reality is much more complicated, with things like caches to take into account. As a result, complexities under O(n) often don't mean much in practice. But the higher you go, the more important it becomes. As you get to O(n^2) it is time to take a hard look at your algorithms, or make really sure that n is small and stays small.
mgradowski 7y ago
Similarly, if you were to write a O(n) Python program displaying the Fibbonacci sequence, it would not run in O(n) time but it would still take O(n) operations. It only makes sense to treat time complexity literally, if operations take fixed amount of time (int addition in Python doesn't).
- adrianN 7y ago
  Int addition never takes constant time unless your ints are bounded by a constant. Which is why serious people use bit complexity, or otherwise take into account the word size of their machines. Very serious people also take into account the number of memory accesses and the amount of memory used, as you can't address arbitrarily large amounts of memory in constant time either.

dpzmick 7y ago

in C, it items[0] could segfault, the fault could be caught by a signal handler which does some unbounded amount of work, then populates the appropriate memory location and returns... More realistically, the page of memory that items[0] is sitting on could be swapped to disk, requiring the OS to do some big operation. trying to write a piece of code with the big-O you are looking for generally has a huge number of caveats. I'm undecided on whether this is a feature (abstraction) or a flaw (easily misleading)

xthestreams 7y ago
I think you (and others) are misunderstanding the purpose of the big-O notation. It is used to discuss about algorithms, not about their implementation.
GuB-42 7y ago
And "print items[0]" is actually O(n) where n is the size of the string. Maybe even O(n^2) if the item is a big number and a binary to decimal conversion is required. But it is doesn't matter here because we have chosen n to be the size of the array, because it is what we are studying. Here it is big-O "constant time" because the execution time doesn't depend on on the size of the array, assuming it is really big. Not that every call of the function will take the same time to run. The reality is much more complicated, with things like caches to take into account. As a result, complexities under O(n) often don't mean much in practice. But the higher you go, the more important it becomes. As you get to O(n^2) it is time to take a hard look at your algorithms, or make really sure that n is small and stays small.

mgradowski 7y ago

Similarly, if you were to write a O(n) Python program displaying the Fibbonacci sequence, it would not run in O(n) time but it would still take O(n) operations. It only makes sense to treat time complexity literally, if operations take fixed amount of time (int addition in Python doesn't).

adrianN 7y ago
Int addition never takes constant time unless your ints are bounded by a constant. Which is why serious people use bit complexity, or otherwise take into account the word size of their machines. Very serious people also take into account the number of memory accesses and the amount of memory used, as you can't address arbitrarily large amounts of memory in constant time either.