i have the following array and i am just trying to make sure that i am right in terms of the time complexity each solution would run

arr = [3,6,8,10,34]

# case one
result_one = [arr[-1], arr[-2], arr[-3]] 
# result = [34, 10, 8]

# case two
result_two = arr[-3:]
# result = [8, 10, 34]

based on the fact that case one is constant O(1) in terms of time complexity, result_two slicing method is linear O(n), case_one will be faster to run. Would this assumption and time complexity of both algorithms correct?

CodePudding user response：

Big-O runtime is about the growth behaviors as n increases. In this case, n can be treated as either the length of arr or the number of items extracted:

• In terms of the number of items extracted, if the number is variable (not just a constant 3) both solutions are O(n). If the number is constant, big-O is meaningless; you're doing a fixed amount of work, that does not change, so growth doesn't even apply.
• In terms of the length of arr, with a constant elements extracted count of 3, both solutions are O(1); aside from the trivial cases of a length 0-2 arr, all arrs of length 3 or greater will require the same amount of work to extract three elements; doubling the size of arr leaves the work unchanged.

No matter how you look at it, both solutions are definitionally the same big-O for any sequence type with O(1) indexing; under the hood, the slice has to do the exact same work as the explicit indexing, so they must perform the same amount of work.

On a sequence type with non-O(1) item lookup (e.g. a linked list or the like, with O(n) lookup), slicing would be superior to repeated indexing for big-O in terms of number of items extracted (because it only has to find the start point of the slice once, not n times, making it O(m n) where m is the size of the linked list and n is the number of items to extract, which simplifies to O(m) since you can't extract more items than you have, while repeated indexing would be O(m*n), paying the O(m) cost n times), but for simple array-like data structures with O(1) indexing, the two will always be big-O equivalent, though the slicing will likely be faster simply because it can do the operation in bulk without bouncing in and out of the Python level code over and over. They'll also behave differently for short inputs; slicing silently returns short outputs if the input has less than three elements, while indexing will die with an IndexError.