3
$\begingroup$

I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the helper methods in my calculations.

If I have an array with a fixed size of 32 indices, and I have a function that sums up the elements in that array, will that function be $O(n)$, or $O(1)$? I think that a function that sums up the elements of an array is $O(n)$ because each element of an $n$-length array must be visited, but if the function only sums up arrays of length 32, is it still $O(n)$?

$\endgroup$
  • $\begingroup$ honestly it's useless to talk about Big O notation when using fixed size input $\endgroup$ – ratchet freak Sep 18 '13 at 8:54
  • $\begingroup$ @ratchetfreak Note the updated question (based on a comment of fvrghi I have removed now); I think the question makes sense. $\endgroup$ – Raphael Sep 18 '13 at 9:50
4
$\begingroup$

There are some things to consider here.

Conceptually, an algorithm that iterates once over the input array has runtime $\Omega(n)$ (and $O(n)$ if it does constant-time work per element), $n$ being the size of the array.

In application, if the algorithm is only ever called with arrays of length $n \leq n_0$ for some constant $n_0$, you may treat the used time as $O(n) \subseteq O(n_0) = O(1)$. Note that the $n$ here is probably not the one you use for your whole algorithm!

In practice, every algorithm runs constant time as real computers have finite memory. This is not an interesting model in the sense that it does not help to differentiate between algorithms that do behave very differently in practice, so we don't use it.

You may be interested in some of our reference questions on asymptotics, runtime analysis and the time used by arithmetic operations.

$\endgroup$
  • $\begingroup$ Finite memory -> constant time? You can let an algorithm run for years. Shouldn't that be constant space? $\endgroup$ – Dukeling Sep 18 '13 at 18:28
  • 1
    $\begingroup$ @Dukeling: Well, inputs are finitely bounded in size, hence there are only finitely many of them and thus [expected] runtimes (for [in expectation] always terminating algorithms) are bounded by a constant, namely the maximum runtime that can be observed. $\endgroup$ – Raphael Sep 18 '13 at 19:09
  • 1
    $\begingroup$ If memory is finite, the number of states of the computation is finite, something like $2^n$ where $n$ is the number of bits you can store (including registers, program counters etc). Either the program stops after $\le 2^n$ steps, or it never stops (once a state appears twice, the program loops). $\endgroup$ – adrianN Sep 19 '13 at 9:18
2
$\begingroup$

Any constant amount of work is O(1), whether it is summing up 32 values or brute forcing a 256 bit AES key.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.