1
$\begingroup$

Lookup tables can convert a piece of computational time into space. I remember that it was a part of a complexity theory course, but I cannot recall how it's called in its terms. I know how to use lookup tables in code to increase performance of my applications, so I don't need a definition of it in common sense.

I want to know a formal definition of an approach like lookup tables in complexity theory.

$\endgroup$

2 Answers 2

0
$\begingroup$

Lookup tables take a key, and either provide a value according to the key or tell you that there is no value under this key.

Time and space requirements will depend on the implementation. It's usually not further mentioned if it is obvious what kind of implementation a reasonable person would use.

$\endgroup$
2
  • $\begingroup$ Sorry, but I've written that I know how to use them, and I'm interested in complexity theory terms $\endgroup$
    – Charlie
    May 29, 2018 at 17:37
  • $\begingroup$ As I said, time and space requirements depend on the implementation. $\endgroup$
    – gnasher729
    May 29, 2018 at 19:09
0
$\begingroup$

In "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak I've found the term space-time tradeoff.

$\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.