. (a) Prove or disprove carefully and in detail: (i) Θ is transitive and (ii) ω is transitive. (b) Assume n is a positive integer. Algorithm A(n: int) int z = 0; int temp = 0; for (int i = 0; i < n ; i++) { for (int j = 0 ; j < i ; j++) { int temp = i + j ; int z = z + temp; } } System.out.println(z) ; What is the input size for Algorithm A? Analyze carefully and explicitly the time complexity of A in terms of the input size. Show all steps. Is A a polynomial time algorithm? Justify your answer.

In the point (i) [tex]\Omega[/tex] is transitive, which means it converts one action to others object because if [tex]\Omega(f(n))=g(n)[/tex] indicates [tex]c.g(n)<=f(n)[/tex]. It's true by definition, that becomes valid. But if [tex]\Omega(g(n))=h(n)[/tex], which implies [tex]c.h(n)<=g(n)[/tex]. it's a very essential component. If [tex]c.h(n) < = g(n) = f(n) \[/tex]. They [tex]\Omega(f(n))[/tex] will also be [tex]h(n)[/tex].

In point (ii), The value of [tex]\Theta[/tex] is convergent since the [tex]\Theta(g(n))=f(n)[/tex]. It means they should be dual a and b constant variable, therefore [tex]a.g(n)<=f(n)<=b.g(n)[/tex] could only be valid for the constant variable, that is [tex]\frac{1}{a}\ \ and\ \ \frac{1}{b}[/tex].

In Option b:

In this algorithm, the input size value is equal to 1 object, and the value of A is a polynomial-time complexity, which is similar to its outcome that is [tex]O(n^{2})[/tex]. It is the outside there will be a loop(i) for n iterations, that is also encoded inside it, the for loop(j), which would be a loop[tex](n^{2})[/tex]. All internal loops operate on a total number of [tex]N^{2}[/tex] generations and therefore the final time complexity is [tex]O(n^{2})[/tex].