What is the time complexity of the original Otsu's method?
The algorithm can certainly be implemented in $O(LN)$ time, as  you say.
It is not hard to optimize it to run in $O(N+L^2)$ time.  Simply form a histogram of pixel intensities (count of the number of pixels of each intensity).  Then you can compute each variance in $O(L)$ time, rather than $O(N)$ time.
You can improve it further to run in $O(N+L)$ time.  Suppose we have computed the sum of values below the threshold and sum of squared values below the threshold; and the same for those above the threshold.  That is enough to compute the standard deviations.  Then, when we bump up the threshold by one, it is possible to update those four sums in $O(1)$ time.  As a result, it takes $O(N)$ time to build the histogram, then $O(L)$ time to compute the score for the first threshold, then $O(1)$ time for each subsequent threshold, and there are $L$ candidate thresholds, for a total of $O(N+L)$ time.
In practice the difference between $O(N+L^2)$ vs $O(N+L)$ might be unimportant, as for 8-bit images, $L \le 256$.