[F-0X]

array.includes(x) is really a function includes(array, x), and this is O(n,1).

[Znafon]

I've never seen Landau's notation with two variables, I don't think it exists. At best you could say it is O(n)*O(1) which is formally equivalent to O(n).

[eru]

You can easily extend Landau's notation to multiple variables (or rather functions of multiple arguments). It's even pretty commonly done, eg a common statement is something like "Getting the k largest elements out of an unsorted input of n elements, takes O(k log n) time, if you use a heap."

> At best you could say it is O(n)*O(1) which is formally equivalent to O(n).

Sorry, that's not how you would use or define multi-variable Big-O notation, if you want it to make any sense.

See eg https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variab... for more details.

[Znafon]

>You can easily extend Landau's notation to multiple variables [...] O(k log n)

Yes, but the parent wrote O(n, 1) not O(n * 1). Does O(k, log n) exists?

> Sorry, that's not how you would use or define multi-variable Big-O notation, if you want it to make any sense.

What do you mean? If I have f: n -> n and g: n -> 1, can I not say O(f) * O(g) = O(f*g) ? See https://math.stackexchange.com/a/2317054 for an example of demonstration.

[eru]

First, the usual way of just writing O(1) or O(n) or O(n^2) is kind of an abuse of notation.

Big-O is a mapping from a function, like O(n -> 1) or (n -> n) or (n -> n^2) or (x -> sin x) to a set of functions.

Function don't care about renaming of arguments. (n -> 2 n) is the same function as (x -> 2 x).

When you write O(k log n) what you really mean is O((k, n) -> k log n)

And you can indeed take it apart:

O((k, n) -> k) * O((k, n) -> log n) == O((k, n) -> n log n)

(For some suitable definition of what multiplication of sets of functions means.)

That's very different from functions with single arguments like in your example.

(And, yes, your example works. It's just a different thing.)