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.

Improve this question
$\endgroup$

2 Answers 2

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

Improve this answer
$\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
    Commented May 29, 2018 at 17:37
  • $\begingroup$ As I said, time and space requirements depend on the implementation. $\endgroup$
    – gnasher729
    Commented 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.

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.