- #1

- 1

- 0

I'm having problems solving this assignment. I don't understand how to solve for big-oh, big omega or big theta.

0.1. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both (in which case f = Θ(g)).

f(n)---------------------g(n)

(a) n - 100------------ n - 200

(b) n^1/2 --------------n^2/3

(c) 100n + log n--------n + (log n)2

(d) n log n-------------10n log 10n

(e) log 2n-------------- log 3n

(f) 10 log n------------- log(n2)

(g) n^1.01-------------- n log^2 n

(h) n^2/log n-----------n(log n)^2

(i) n^0.1----------------(log n)^10

(j) (log n)^log n--------- n/log n

(k) sq root of n----------(log n)^3

(l) n^1/2 ---------------5^log2 n

(m) n2^n-------------------3^n

(n) 2^n------------------ 2^n+1

(o) n!----------------------2^n

(p) (log n)^log n------- 2^(log2 n)^2

0.2. Show that, if c is a positive real number, then g(n) = 1 + c + c2 + . . . + c^n is:

(a) Θ(1) if c < 1.

(b) Θ(n) if c = 1.

(c) Θ(c^n) if c > 1.

The dashes in the first problem are only meant to separate the two columns for visibility.

What I know is this. f = O(g) means f <= g. f = Ω(g) means g = O(f). f = Θ(g) means f = O(g) and f = Ω(g). I'm a little confused right now, I'd appreciate some help.

0.1. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both (in which case f = Θ(g)).

f(n)---------------------g(n)

(a) n - 100------------ n - 200

(b) n^1/2 --------------n^2/3

(c) 100n + log n--------n + (log n)2

(d) n log n-------------10n log 10n

(e) log 2n-------------- log 3n

(f) 10 log n------------- log(n2)

(g) n^1.01-------------- n log^2 n

(h) n^2/log n-----------n(log n)^2

(i) n^0.1----------------(log n)^10

(j) (log n)^log n--------- n/log n

(k) sq root of n----------(log n)^3

(l) n^1/2 ---------------5^log2 n

(m) n2^n-------------------3^n

(n) 2^n------------------ 2^n+1

(o) n!----------------------2^n

(p) (log n)^log n------- 2^(log2 n)^2

0.2. Show that, if c is a positive real number, then g(n) = 1 + c + c2 + . . . + c^n is:

(a) Θ(1) if c < 1.

(b) Θ(n) if c = 1.

(c) Θ(c^n) if c > 1.

The dashes in the first problem are only meant to separate the two columns for visibility.

What I know is this. f = O(g) means f <= g. f = Ω(g) means g = O(f). f = Θ(g) means f = O(g) and f = Ω(g). I'm a little confused right now, I'd appreciate some help.

Last edited: