CS136 Study Guide - Big O Notation, Indeterminate Form
Document Summary
Answer: functions which are always zero past a certain point. (cid:1) o(n2). 2 and n0 = 2 in the formal de nition to get(cid:0)n. 2 n2 for all n 2, so we can take c = 1. Proof: for positive n, n2 n2 + 2 (cid:16) So we can take c = 2 and n0 = 1 in the formal de nition to get n2 o(en). Proof: for n 1, n n n n = nn. So we can take c = 1 and n0 = 1 in the formal de nition to get n! 1: f (n) (g(n)) f (n) o(g(n)) and f (n) (g(n)) Proof: note that n 2 = 1. 4 n2 (divide by 4) (multiply by n 0) (multiply by 1) Then for n 2, (cid:19) (cid:18)n (cid:1) o(n2) we in fact have(cid:0)n. 4 and n0 = 2 in the formal de nition to get(cid:0)n n2 1. 4 n2. (cid:1) (n2). (cid:1) (n2).
