Algorithms Use the informal definitions of O Theta and Ohm t

Algorithms:

Use the informal definitions of O, Theta, and Ohm to determine whether the following assertions are true or false. n(n + 1)/2 O(n3) n(n + 1)/2 O(n2) n(n + 1)/2 Theta(n3) n(n + 1)/2 Ohm(n)

Solution

Answer:

a) n(n+1)/2 belongs to O(n^3)

Proof :

Here f(n) = n(n+1)/2 , g(n) = n^3

by the definition of big O:

F(n) < = c* g(n) , where c is constant and is greater than 1

n(n+1)/2 < = c*n^3

(n^2 +n)/2 < = c*n^3

let c =1

(n^2 + n)/2 < = n^3

If(n) is highest power is 2 not 3 , so its big O is n^2 ,not n^3 , so it is false

b) n(n+1)/2 belongs to O(n)

Proof :

As proved from the part(a) that f(n) = O(n^2) not n^3 , so it is true here.

c) n(n+1)/2 belongs to theta(n^3)

Proof : we know that theta gives the best case , but here it is giving worst case , the best case is theta(n) here not theta(n^3)

as from the definition c1*g(n) < = f(n) < = c2*g(n)

theta(n^3) is not a tight bound here , but theta(n). so it is false

d) n(n+1)/2 belongs to omega(n)

It is true , it gives the best case , the best case possible could be omega(n) not omega(n^2) . So from the function f(n) = (n^2 +n)/2 , the best case we could take is omega(n) , so it is true