CS 341: Foundations of Computer Science II Prof. Marvin ...

CS 341: Foundations of Computer Science II Prof. Marvin Nakayama Homework 11 Solutions 1.Answer each part TRUE or FALSE. (a) 2n = O(n). TRUE. We can see this by letting c = 2, and noting that 2n cn = 2n for all n 1. Thus, the de nition of big-O holds for c = 2 and n 0 = 1. (b) n2 = O(n). FALSE. For it to be true, we would need that there exist ... ................
................