Это займет время, пропорциональное, по крайней мере, n * 2 ^ n. Каждый из пропозициональных символов может принимать одно из двух значений - истинное или ложное. Часть таблицы истинности, которая перечисляет все возможные назначения n таких переменных, должна иметь по крайней мере 2 * 2 *… * 2 (n раз) = 2 ^ n строк по n записей в каждой; и это даже не считая подвыражения, которые составляют остальную часть таблицы. Эта нижняя граница является жесткой, поскольку мы можем представить себе предложение P1 и P2 и… и Pn и следующую процедуру, требующую времени Theta (n * 2 ^ n) для записи ответа:
fill up P1's column with 2^(n-1) TRUE and then 2^(n-1) FALSE
fill up P2's column with 2^(n-2) TRUE and then 2^(n-2) FALSE, alternating
…
fill up Pn's column with 1 TRUE and 1 FALSE, alternating
fill up the last column with a TRUE at the top and FALSE all the way down
Если у вас есть более сложные предложения, тогда вы, вероятно, должны принять число подвыражений в качестве другой независимой переменной, поскольку это может иметь асимптотически релевантный эффект (используя n пропозициональных символов, вы можете иметь произвольное количество уникальных подвыражений, которым должны быть даны свои собственные столбцы в полной таблице истинности) .