Orders of Complexity

Question 1

log n

log^<em>c</em> n

Answer 1

log n = O(log^c n)

log^c n = Ω(log n)

Question 2

log^c n

n^<em>c</em>

Answer 2

log^c n = O(n^<em>c</em>)

n^<em>c</em> = Ω(log^c n)

(note that for n^<em>c</em>, c > 0)

Question 3

log n

n^1/2

Answer 3

log n = O(n^1/2)

n^1/2 = Ω(log n)

Question 4

n^<em>c</em>

n log n

Answer 4

if c = 1:
n^<em>c</em> O(n log n)
n log n Ω(n^<em>c</em>)

if c > 1
n log n O(n^<em>c</em>)
n^<em>c</em> Ω(n log n)

Question 5

n²

n log n

Answer 5

n log n O(n2)

n² Ω(n log n)

Question 6

c^<em>n</em>

n^<em>c</em>

Answer 6

n^<em>c</em> O(c^<em>n</em>)

c^<em>n</em> Ω(n^<em>c</em>)

Question 7

n log n

log^<em>c</em> n

Answer 7

log^c n O(n log n)

n log n Ω(log^c n)

Question 8

n^1/2

n²

Answer 8

n^1/2 O(n²)

n² Ω(n^1/2)