[jamesb1]

Suppose you want to prove the symmetry of the Theta Relation.. which of course, means that f theta(g) implies g theta(f).
Do c1 and c2 (the two constants) have to be the same for both f theta(g) and g theta(f)?

Also when you come to prove these relations (including O and Omega), by showing that they're reflexive, symmetric and transitive, the statements usually start with the quantifier "For all", this confuses me a lot.. Does this mean that these properties apply for ALL instances of f(n) and g(n), for example if f = n^2 and g = n^3 are Theta related, does that mean that this applies for all functions in f(n) and g(n) (ex. f = n^3 and g = n^2 is also theta related?)

Thanks in advance, James

[mojo666]

jamesb1, on 17 November 2011 - 01:47 PM, said:

Suppose you want to prove the symmetry of the Theta Relation.. which of course, means that f theta(g) implies g theta(f).
Do c1 and c2 (the two constants) have to be the same for both f theta(g) and g theta(f)?

I don't think so.

Quote

Also when you come to prove these relations (including O and Omega), by showing that they're reflexive, symmetric and transitive, the statements usually start with the quantifier "For all", this confuses me a lot.. Does this mean that these properties apply for ALL instances of f(n) and g(n), for example if f = n^2 and g = n^3 are Theta related, does that mean that this applies for all functions in f(n) and g(n) (ex. f = n^3 and g = n^2 is also theta related?)

It depends on what follows the "For all". I've never seen "For all f(n) in A, something". Usually it is "For all n in A, something about f(n)" which just means "for every possible input". Is the statement from your example something like "For all n in A, f(n)=Theta(g(n))"? This does not mean "all functions". It means "all inputs to f and g". f and g are defined to each be one particular function.