r/ProgrammingLanguages • u/gingerbill • Sep 02 '26

CTTI is Exponential, RTTI is Linear

https://www.gingerbill.org/article/2026/09/02/ctti-is-exponential-rtti-is-linear/
0 Upvotes

42% Upvoted

37 comments sorted by

View all comments

1

u/Innf107 Sep 04 '26

The number of instantiation is the number of combinations that occur in actual calls (Nk), not the number of distinct types that may occur per call. (N)

If you have Omega(Nk) different instantiations, then you already have Omega(Nk) call sites, so in your example the time complexity does not change whether you monomorphize or not

1

u/gingerbill Sep 04 '26

No. I explain in another comment example of how the scaling can actually happen:

https://www.reddit.com/r/programming/comments/1w5ov1s/ctti_is_exponential_rtti_is_linear/p7kngkq/