Question

Can I get some help please :)

8. Determine whether or not the following are true and provide a full derivation explaining your answer for each. The domain of the functions of n below is the positive real numbers. For convenience, you may assume that the logs are in the base of your choice, but you should specify what base you are using in your derivation. (2 marks each) a. 6+n+is O(n3) b. 5(n log n +n) is O(n2) c. 6? + 5n3 + log n is ?(n*) d. (2n - 4)2 is e(n3) e. 4n2 -5+9n is 0(n) logu3) is O(n) g. logG+n*) is 0(n) h. 8n2 is 2(n2) 4

Answer 1

Before starting let's have a look at Big-O and Big-Omega and Theta:

a)

6+n+1/n

comparing 6+n+1/n and n^3 we can see that

6+n+1/n <= c * n^3

for c>0,

The inequality holds true.

This means that

6+n+1/n = O(n^3)

The statement is true.

b)

5(n log n + n)

comparing 5(n log n + n) and n^2

we can see that

5(n log n + n) <= c * n^2

for c>0, the inequality holds true

this means that

5(n log n + n)= O(n^2)

The statement is true.

c)

6n^2 + 5n^3 + log n

comparing 6n^2 + 5n^3 + log n and n^3 we can see that

6n^2 + 5n^3 + log n >= c * n^3

for c>0,

The inequality holds true.

This means that

6n^2 + 5n^3 + log n = $\Omega$(n^3)

The statement is true.

d)

(2n-4)^2 can also be written as

4n^2 + 16 - 4n

comparing 4n^2 + 16 - 4n and n^3 we can see that

4n^2 + 16 - 4n <= c * n^3

for c>0,

The inequality holds true.

This means that

4n^2 + 16 - 4n? = O(n^3)

but

the inequlity

4n^2 + 16 - 4n >= c * n^3

doen't hold true for any value of c

this means that 4n^2 + 16 - 4n $\neq \Omega$ (n^3)

WHich manes This statement is false.