4 ms·
That effectively does make it exponential x * x === x^2
by smfjaw 3y ago
That effectively does make it exponential
x * x === x^2
- ksarw 3y agoby going exponential, they mean 2^x; x^2 can still be the same "size" as x
- NobodyNada 3y agox^2 is not exponential; it's quadratic. 2^x is an example of an exponential function. The parent comment was alluding to the idea of set cardinality (https://en.wikipedia.org/wiki/Cardinality https://en.wikipedia.org/wiki/Cardinality). Two sets have the same cardinality if you can establish a bijection (a one-to-one mapping) between elements of one set and elements of the other. The set of all natural numbers is said to have a "countably infinite" cardinality. It turns out that for any countably infinite set S, the set S x S is also countably infinite (see Hilbert's hotel: https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gra...). For example, the set of 2-tuples of natural numbers (1, 1), (1, 2), (1, 3), ..., (2, 1), (2, 2), ... is the same size as the set of natural numbers. So in this sense, "endless*endless = endless". Whereas the set of infinitely-long tuples of natural numbers is "uncountably infinite;" it has a cardinality greater than that of the set of natural numbers. Thus, "you have to go exponential"; i.e. "endless^endless".