Studying an algorithm's resource use under a stated cost model. Time complexity, space complexity and amortized analysis answer different questions, so an operation count should specify the input-size parameter and what each primitive operation costs.
A method for proving that an algorithm must perform a certain amount of work: supply observations compatible with more than one possible input until enough information has been acquired to distinguish the required outputs. For exact membership in an arbitrary array, answering every inspected location with a value other than the target forces inspection of every location in the absent case, since any uninspected location could contain the target.
Articles by others on the same topic
There are currently no matching articles.