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)$?

Improve this question
$\endgroup$
2
  • $\begingroup$ honestly it's useless to talk about Big O notation when using fixed size input $\endgroup$
    – ratchet freak
    Commented Sep 18, 2013 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
    Commented Sep 18, 2013 at 9:50

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Finite memory -> constant time? You can let an algorithm run for years. Shouldn't that be constant space? $\endgroup$
    – Bernhard Barker
    Commented Sep 18, 2013 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
    Commented Sep 18, 2013 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
    Commented Sep 19, 2013 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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