Why does Big-O Notation use O(1) instead of O(k)?

Question

If I understand Big-O notation correctly, `k` should be a constant time for the efficiency of an algorithm. Why would a constant time be considered `O(1)` rather than `O(k)`, considering it takes a variable time? Linear growth `( O(n + k) )` uses this variable to shift the time right by a specific amount of time, so why not the same for constant complexity?

Accepted Answer

There is no such linear growth asymptotic `O(n + k)` where `k` is a constant. If `k` were a constant and you went back to the limit representation of algorithmic growth rates, you'd see that `O(n + k) = O(n)` because constants drop out in limits.

Your answer may be `O(n + k)` due to a variable `k` that is fundamentally independent of the other input set `n`. You see this commonly in compares vs moves in sorting algorithm analysis.

To try to answer your question about why we drop `k` in Big-O notation (which I think is taught poorly, leading to all this confusion), one definition (as I recall) of O() is as follows:

```
Read: f(n) is in O( g(n) ) iff there exists d and n_0 where for all n > n_0,
                                         f(n) <= d * g(n)
```

Let's try to apply it to our problem here where k is a constant and thus f(x) = k and g(x) = 1.

- Is there a `d` and `n_0` that exist to satisfy these requirements?

Trivially, the answer is of course yes. Choose d > `k` and for n > 0, the definition holds.

Why does Big-O Notation use O(1) instead of O(k)?

Solution

Problem