4-1 Recurrence examples¶
Give asymptotically tight upper and lower bounds for T .n/ in each of the following algorithmic recurrences. Justify your answers. a. T .n/ D 2T .n=2/ C n3 . b. T .n/ D T .8n=11/ C n. c. T .n/ D 16T .n=4/ C n2 . d. T .n/ D 4T .n=2/ C n2 lg n. e. T .n/ D 8T .n=3/ C n2 . f. T .n/ D 7T .n=2/ C n2 lg n. g. T .n/ D 2T .n=4/ C pn. h. T .n/ D T .n 2/ C n2 .