💾 Archived View for ajdiaz.me › doc › 2016 › 02121-iteration-demostration.txt captured on 2024-09-28 at 23:58:34.
⬅️ Previous capture (2022-06-04)
-=-=-=-=-=-=-
Basic demostration of complexity of iteration over a list
http://ajdiaz.me/doc/2016/02121-iteration-demostration.txt
Version: 2016-02-12
During a conversation with my colleages about the complexity of an algorithm
which requires to iterate a long list of elements, we talk about the
posibility of that algorithm was squared time complexity due to the way tht
it was implemented, but we stop a while thinking if any iteration over all
elements of any set (or sorted set) could be less than O(n).
It's obvious that is not possible, because you need to read all elements in
order to get all elements, but I realized that, actually, I don't have any
proof of that, just common sense.
This demonstration try to find a mathematical proof of that.
Hypothesis
a) Let ℕ = {x ∈ ℤ, x > 0}
b) Let L = {x₁..xₙ₊₁}, |L| = n
c) Let f: ℕ → S ⊆ L / f(1, t) = {x₁..xₜ}, t > 0 and t < n+1
Demostration by induction
- Demostration for f(1)
f(1) = {x} ⇒ O(f(1)) = O(1)
- Supposition for f(k)
f(k) = O(k)
- Demostration for f(k+1)
f(k+1) = {x₁..xₖ₊₁}
= {x₁..xₖ} ∪ {xₖ₊₁}
{Leibniz}
= f(k) ∪ f(k+1)
{Landau}
= max({O(k), O(k+1)})
= O(n)
Conclussion
Iteration over all elements of a set (sorted or not), requires a O(n) of
time complexity in all cases.