algorithm

Question

how do find which notations satisfy what properties

for example : big O doesnt satisfy symmetric but satisfies reflexive and transitive

how can this be found for various notations

Answer 1

do like that let's for,,,, big O

lets A=O(B) ie. A<=B

a) reflexive:

A<=A ........which is satisfied so reflexive

b) symmetric:

A<=B which is not implied to B<=A .............so not symmetric

c) transitive:

A<=B and B<=C  which is implied A<=C..........so transitive

 do same for omega and theeta notation

omega satisfied reflexive and transitive property

theeta satisfied reflexive, symmetric and transitive property

Comments

why O and Ʊ not symmetric ?? pawan kumarln