Answer to Question #260077 in Algorithms for kriti

Question

Represent the following function in form of big-oh(O) and omega(Ω) and theta(Ө)  notation. Find the required constants for it.

1. 2n2 + 25nlogn
2. 3 n3 + 4n + 11
3. 5 n3 +  n2 + 3n + 2
4. 2*2n + 6 n2 + 3n
5. 3*n3 – 4n
6. 4n4 + n + n2logn
7. ½ n2 +3n

4n2+7n+3n 3.5

Answer 1

Big-Oh Notation Let f and g be functions from positive numbers to positive numbers.

f(n) is O(g(n)) if there are positive constants C and k such that: f(n) ≤ C g(n) whenever n > k f(n) is O(g(n)) ≡ ∃C ∃k ∀n (n > k → f(n) ≤ C g(n))

To prove big-Oh, choose values for C and k and prove n > k implies f(n) ≤ C g(n)