Lodash indexOf vs lastIndexOf Time Complexity

This article examines the algorithmic time complexity of _.indexOf and _.lastIndexOf in the Lodash JavaScript library. It explains how both methods operate under the hood, compares their theoretical performance metrics, and clarifies the practical differences between searching an array from the beginning versus the end.

Theoretical Time Complexity

In terms of asymptotic Big-O notation, there is no difference in algorithmic time complexity between _.indexOf and _.lastIndexOf:

• Worst-Case Complexity: \(O(n)\)
• Average-Case Complexity: \(O(n)\)
• Best-Case Complexity: \(O(1)\)
• Space Complexity: \(O(1)\)

In both algorithms, \(n\) represents the length of the input array. In the worst-case scenario—such as when the target element does not exist in the array—both methods must traverse the entire array, examining each element exactly once. This linear traversal requires \(O(n)\) operations. The space complexity remains \(O(1)\) because both methods iterate iteratively using pointers without allocating additional memory proportional to the array size.

How _.indexOf Operates

The _.indexOf method searches an array from left to right (from index 0 toward index n - 1, unless a custom fromIndex is specified).

• Best Case (\(O(1)\)): The target element is located at the very start of the search (index 0). The loop terminates immediately.
• Worst Case (\(O(n)\)): The target value is located at the final index (n - 1) or is not present in the array at all, forcing the search to inspect all \(n\) items.

(Note: While Lodash provides a separate method called _.sortedIndexOf for sorted arrays that operates in \(O(\log n)\) using binary search, the standard _.indexOf method performs a strict linear scan.)

How _.lastIndexOf Operates

The _.lastIndexOf method performs the exact reverse operation, searching from right to left (from index n - 1 toward index 0).

• Best Case (\(O(1)\)): The target element is located at the very end of the array (index n - 1). The function returns on the first iteration.
• Worst Case (\(O(n)\)): The target value is at the first index (0) or does not exist in the array, requiring a full traversal of all \(n\) elements.

Practical Differences

While their Big-O theoretical classifications are identical, the practical performance depends on where the desired data is distributed in the array:

1. Duplicate Values: If an array contains multiple instances of a value, _.indexOf finds the first occurrence, while _.lastIndexOf finds the final occurrence.
2. Data Insertion Patterns: If you are querying items in an append-only collection (such as an event log), recent entries are located near the end of the array. Using _.lastIndexOf will often yield an early exit, resulting in practical execution times closer to \(O(1)\) rather than \(O(n)\). Conversely, items likely to be near the front will resolve faster using _.indexOf.