News for hackers. Stuff that matters.

A comment on Fast constant-time GCD algorithm and modular inversion. Parent comment

Re:Fast constant-time GCD algorithm and modular inversion by throwawaymath on Thursday June 13, 2019 @09:51AM (#20174810)
> I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time.

With respect, I think you may misunderstand the meaning of "constant time" in the sense of complexity theory, i.e. O(1). Accessing an element in an array of size n is a constant time operation. See: https://stackoverflow.com/questions/7297916/why-does-accessi...

EDIT: Corrected "search" to "access"

[ Parent | on HN ]
Re:Fast constant-time GCD algorithm and modular inversion by Drod718 on Thursday June 13, 2019 @10:24AM (#20175145)
Wouldn’t searching for an element in an arbitrary array of size n happen in O(n) time, while only accessing it is considered O(1)? I could understand the search case for something like a hash table being O(1) but does that also apply to your standard array?
[ Parent | on HN ]
Re:Fast constant-time GCD algorithm and modular inversion by throwawaymath on Thursday June 13, 2019 @10:42AM (#20175332)
Ah, I misspoke. I meant "access", you're correct about searching. The original link I cited for explanation still applies.
[ Parent | on HN ]