CODEWITHSUNDEEP
algorithm
invisal
invisal

Reputation: 11181

Is it O(n^2) or O(1)?

Is the execution time of this unique string function reduced from the naive O(n^2) approach?

This question has a lot of interesting discussion leads me to wonder if we put some threshold on the algorithm, would it change the Big-O running time complexity? For example:

void someAlgorithm(n) {
    if (n < SOME_THRESHOLD) {
         // do O(n^2) algorithm
    }
}

Would it be O(n2) or would it be O(1).

Upvotes: 1

Views: 381

Answers (2)

Anthony
Anthony

Reputation: 12407

If SOME_THRESHOLD is constant, then you've hard coded a constant upper bound on the growth of the function (and f(x) = O (g(x)) gives an upper bound of g(x) on the growth of f(x)).

By convention, O(k) for some constant k is just O(1) because we don't care about constant factors.

Note that the lower bound is unknown, a least theoretically, because we don't know anything about the lower bound of the O(n^2) function. We know that for f(x) = Omega(h(x)), h(x) <= 1 because f(x) = O(1). Less than constant-time functions are possible in theory, although in practice h(x) = 1, so f(x) = Omega(1).

What all this means is by forcing a constant upper bound on the function, the function now has a tight bound: f(x) = Theta(1).

Upvotes: 0

Ishamael
Ishamael

Reputation: 12795

This would be O(1), because there's a constant, such that no matter how big the input is, your algorithm will finish under a time that is smaller than that constant.

Technically, it is also O(n^2), because there's a constant c such that no matter how big your input is, your algorithm will finish under c * n ^ 2 time units. Since big-O gives you the upper bound, everything that is O(1) is also O(n^2)

Upvotes: 13

Related Questions