Algorithm Analysis - Tran Ba Tuan - HUS - VNU

(1) What is Algorithm Complexity

Algorithm complexity refers to the computational resources an algorithm requires to solve a problem, typically in terms of time and space. It is usually analyzed based on:

Time Complexity: This measures the amount of time an algorithm takes as a function of the input size (denoted as n). The time complexity is expressed using Big-O notation, which describes the upper bound of the running time. Common complexities include:

• \(O(1):\) Constant time
• \(O(log n):\) Logarithmic time
• \(O(n):\) Linear time
• \(O(n log n):\) Linearithmic time
• \(O(n²):\) Quadratic time
• \(O(2^n):\) Exponential time
• \(O(n!):\) Factorial time

Space Complexity: This measures the amount of memory an algorithm uses relative to the input size. It is also expressed in Big-O notation, capturing how additional memory grows as input size increases.

Efficient algorithms strive for low time and space complexity, ensuring scalability and performance when dealing with larger datasets.

(2) Examples: Upper bound

Example 1. What is the Upper bound for:

a, We are given the function:

\[f(n) = 3n + 5\]

• As \(n\) increases, the linear term \(3n\) dominates the constant \(5\).
• The constant \(3\) in front of \(n\) can be ignored because Big-O notation focuses on the order of growth, not constant factors.
• Answer: \(O(f(n)) = O(n)\)

b, We are given the function:

\[f(n) = 4n^2 + 3\]

• As \(n\) increases, the quadratic term \(4n^2\) dominates the constant \(3\).
• The coefficient \(4\) can be ignored in Big-O notation.
• Answer: \(O(f(n)) = O(n^2)\)

c, We are given the function:

\[f(n) = n^4 + 100n^2 + 80\]

• As \(n\) increases, the term \(n^4\) grows faster than \(100n^2\) and \(80\), so it dominates the function.
• The coefficients \(100\) and \(80\) are constants and can be ignored.
• Answer: \(O(f(n)) = O(n^4)\)

d, We are given the function:

\[f(n) = 5n^3 - 5n^2\]

• As \(n\) increases, the cubic term \(5n^3\) dominates the quadratic term \(-5n^2\).
• The coefficient \(5\) can be ignored in Big-O notation.
• Answer: \(O(f(n)) = O(n^3)\)

e, We are given the function:

\[f(n) = 502\]

• This is a constant function; it does not depend on \(n\) and remains the same regardless of input size.
• For constant functions, the upper bound is \(O(1)\), meaning the function has constant time complexity.
• Answer: \(O(f(n)) = O(1)\)

(2) Examples: Time complexity

General question: What is the time complexity?

Example 2. Calculate \(S\):

\[S = \frac{n(n-1)}{2}\]

• This is kind of a trick question. This is ONE independent operation, no loops involved, and the actual value of \(n\) does not matter, so It has a time complexity of \(O(1)\)
• Time Complexity: \(O(1)\)

Example 3.

for i in range(0, n):
    print('Current Number', i)

• The loop runs from \(0\) to \(n - 1\), so the number of iterations is \(n\), and there is a single print operation per iteration.
• Time Complexity: \(O(n)\)

Example 4.

for i in range(0, n):
    print('Current Number', i)
    break

• The loop seems to be similar to Example 3., but there is a break statement right after the very first operation. Therefore, the loop will be terminated on the very first iteration.
• Time Complexity: \(O(1)\)

Example 5.

def function(n):
    i = 1
    while i <= n:
        i = i * 2
        print(i)
function(100)

• In this function, there is a loop running from \(i = 1\) to \(n\). However, inside the loop itself, the value of \(i\) doubles with each iteration, so the number of iterations is logarithmic with respect to \(n\).
• Time Complexity: \(O(log(n))\)

Example 6.

for i in range(0, n):
    for j in range(0, n):
        print("Value of i, j", i, j)

• In this case, we can clearly see that there are two loops, each going from \(0\) to \(n - 1\), so there are \(n \times n = n^2\) total iterations.
• Time Complexity: \(O(n^2)\)

Example 7.

public void function(int n) {
    int i, j, k, count = 0;
    for(i = n/2; i <= n; i++)
        for(j = 1; j + n/2 <= n; j++)
            for(k = 1; k <= n; k = k * 2)
                count++;
}

• The outer loop runs from \(i = n/2\) to \(n\), so it executes \(n/2\) times, which is \(O(n)\).
• The middle loop runs \(n/2\) times.
• The innermost loop doubles \(k\) each time, so it runs \(O(log(n))\) times.
• The total time complexity is the product of all three loops:

• Time Complexity: \(O(n^2log(n))\)

Example 8.

public void function(int n) {
    int i, j, k, count = 0;
    for(i = n/2; i <= n; i++)
        for(j = 1; j <= n; j = 2 * j)
            for(k = 1; k <= n; k = k * 2)
                count++;
}

• The outer loop runs from \(i = n/2\) to \(n\), so it executes \(n/2\) times, which is \(O(n)\).
• The middle loop doubles \(j\) each time, so it runs \(O(log(n))\) times.
• The innermost loop doubles \(k\) each time, so it runs \(O(log(n))\) times.
• The total time complexity is the product of all three loops:

• Time Complexity: \(O(n log^2(n))\)

(3) Practice: Time complexity

Exercise 1. What is the algorithm complexity?

a, We are given the function:

\[T(n) = nlogn + 3n + 2\]

• We have three terms: \(nlogn\), \(3n\), and \(2\).
• The dominant term is \(nlogn\) as it grows faster than \(n\) for large values of \(n\).
• The constant terms and lower-order terms ($ 3n $ and $ 2 $) are dropped in Big O notation.
• Therefore, the complexity is \(O(n log(n))\).
• Answer: \(O(n log(n))\)

b, We are given the function:

\[T(n) = nlog(n!) + 5n^2 + 7\]

• We have three terms here: \(nlog(n!)\), \(5n^2\), and \(7\).
• Note that \(log(n!)\) is \(O(n log n)\) (this is a mathematical fact).
• So, \(nlog(n!)\) is actually \(O(n^2 log n)\).
• However, for very large \(n\), \(n^2\) grows faster than \(n^2 log n\).
• The constant terms (5 and 7) are dropped in Big O notation.
• Therefore, the overall time complexity is dominated by \(n^2\), giving us \(O(n^2)\).
• Answer: \(O(n^2)\)

c, We are given the function:

\[T(n) = 1000n + 0.01n^2\]

• We have two terms: \(1000n\) and \(0.01n^2\).
• Although \(1000n\) has a larger coefficient, \(n^2\) grows much faster for large values of \(n\).
• In Big O notation, we’re concerned with the growth rate for large \(n\), not the coefficients.
• Therefore, \(n^2\) dominates, and the time complexity is \(O(n^2)\).
• Answer: \(O(n^2)\)

d, We are given the function:

\[T(n) = 100nlogn + n^3 + 100n\]

• We have three terms: \(100nlogn\), \(n^3\), and \(100n\).
• For large values of \(n\), \(n^3\) grows much faster than both \(nlogn\) and \(n\).
• The constants (100) are dropped in Big O notation.
• Therefore, the time complexity is dominated by \(n^3\), giving us \(O(n^3)\).
• Answer: \(O(n^3)\)

e, We are given the function:

\[T(n) = 0.01nlogn + n(logn)^2\]

• We have two terms: \(0.01nlogn\) and \(n(logn)^2\).
• \(n(logn)^2\) grows faster than \(nlogn\) for large \(n\).
• The constant (0.01) is dropped in Big O notation.
• Therefore, the time complexity is \(O(n log^2 n)\).
• Answer: \(O(n log^2 n)\)

Exercise 2. What is the time complexity?

a, Given method:

// Returns the sum of the integers in given array .
public static int example1(int[] arr) {
    int n = arr.length, total = 0;
    for (int j = 0; j < n; j++) // loop from 0 to n -1
        total += arr[j];
    return total;
}

• This function has a single loop that iterates from \(0\) to \(n-1\).
• The number of iterations is directly proportional to the size of the input array \((n)\).
• Each iteration performs a constant-time operation (addition).
• Therefore, the time complexity is linear, \(O(n)\).
• Answer: \(O(n)\)

b, Given method:

// Returns the sum of the integers with even index in given array .
public static int example2(int[] arr) {
    int n = arr.length, total = 0;
    for (int j = 0; j < n; j += 2) // note the increment of 2
        total += arr [j];
    return total;
}

• This function has a loop that iterates over every other element of the array.
• Although it processes only half of the elements, in Big O notation, we still consider this linear time.
• The number of operations is still directly proportional to \(n\), just with a factor of (1/2).
• Constants are dropped in Big O notation, so \(O(n/2)\) simplifies to \(O(n)\).
• Answer: \(O(n)\)

c, Given method:

// Returns the sum of the prefix sums of given array .
public static int example3(int[] arr) {
    int n = arr.length, total = 0;
    for (int j = 0; j < n ; j++) // loop from 0 to n -1
        for (int k = 0; k <= j; k++) // loop from 0 to j
            total += arr [j];
    return total;
}

• This function has two nested loops.
• The outer loop runs \(n\) times.
• For each iteration of the outer loop, the inner loop runs \(j + 1\) times, where \(j\) goes from \(0\) to \(n-1\).
• The total number of iterations is the sum of integers from \(1\) to \(n\), which is \(n(n+1)/2\).
• This simplifies to \(O(n^2)\) in Big O notation.
• Answer: \(O(n^2)\)

d, Given method:

// Returns the sum of the prefix sums of given array .
public static int example4(int[] arr) {
    int n = arr.length, prefix = 0, total = 0;
    for (int j = 0; j < n; j++) { // loop from 0 to n -1
        prefix += arr [j];
        total += prefix;
    }
    return total;
}

• This function has a single loop that iterates \(n\) times.
• Inside the loop, all operations (addition and assignment) are constant time.
• Although it’s calculating prefix sums, it does so efficiently in a single pass through the array.
• Therefore, the time complexity is linear, \(O(n)\)
• Answer: \(O(n)\)

e, Given method:

// Returns the number of times second array stores sum of prefix sums from first
public static int example5(int[] first, int[] second) {
    // assume equal - length arrays
    int n = first.length, count = 0;
    for (int i = 0; i < n; i++) { // loop from 0 to n -1
        int total = 0;
        for (int j = 0; j < n; j++) // loop from 0 to n -1
            for (int k = 0; k <= j; k++) // loop from 0 to j
                total += first [k];
                if (second [i] == total) count++;
    }
    return count;
}

• This function has three nested loops.
• The outermost loop runs \(n\) times.
• For each iteration of the outer loop, the middle loop runs \(n\) times.
• For each iteration of the middle loop, the innermost loop runs \(j + 1\) times, where \(j\) goes from \(0\) to \(n-1\).
• The total number of iterations is approximately \(n * n * (n/2) = n^3/2\).
• In Big O notation, this simplifies to \(O(n^3)\).
• Answer: \(O(n^3)\)

(4) Practice: Master theorem

(Master theorem) If \(n\) is a power of \(b\), the solution to the recurrence:

\[T(n) = \begin{cases} aT(n/b) + n^d & \text{if } n > 1 \text{ and } a \geq 1, b > 1, d \geq 0 \quad \\ 1 & \text{if } n \leq 1\end{cases}\]

is denoted:

\[T(n) = \begin{cases} O(n^d) & \text{if } a < b^d \\ O(n^d \log(n)) & \text{if } a = b^d \\ O(n^{\log_b(a)}) & \text{if } a > b^d \end{cases}\]

Example 9. Determine algorithm complexity of this expression:

\[T(n) = \begin{cases} 2T(n-1) - 1 & \text{if } n > 0 \\ 1 & \text{otherwise} \end{cases}\]

\[\begin{flalign*} &\text{Let: } T(n-1) = 2T(n-2) - 1 \\ &\Rightarrow T(n) = 2(2T(n-2) - 1) - 1 \qquad (1) \quad\\ &= 4T(n-2) - 3 \\[10pt] &\text{Let: } T(n-2) = 2T(n-3) - 1 \\ &\Rightarrow T(n) = 8T(n-3) - 7 \qquad (2)\\[10pt] &\text{From (1), (2): } \\ &T(n) = 2^k T(n-k)-(2^k - 1) \\[10pt] &\text{Let k = n: } \\ &T(n) = 2^n T(0) - (2^n - 1) \\ &= 2^n . 1 - (2^n - 1) = 2^n - 2^n + 1 = 1 \\[10pt] &\Rightarrow T(n) = O(1) \\ \end{flalign*}\]

Example 10. Determine algorithm complexity of this expression:

\[T(n) = \begin{cases} 3T(n-1) & \text{if } n > 0 \\ 1 & \text{otherwise} \end{cases}\]

\[\begin{flalign*} &\text{Let: } T(n-1) = 3T(n-2) \\ &\Rightarrow T(n) = 3(3T(n-2)) = 3^2 T(n-2) \qquad (1) \quad \\[10pt] &\text{Let: } T(n-2) = 3T(n-3) \\ &\Rightarrow T(n) = 3^3 T(n-3) \qquad (2) \quad \\[10pt] &\text{From (1), (2): } \\ &T(n) = 3^k T(n-k) \\[10pt] &\text{Let k = n: } \\ &T(n) = 3^n T(0) = 3^n \\[10pt] &\Rightarrow T(n) = O(3^n) \\ \end{flalign*}\]

Example 11. Determine algorithm complexity:

1. Given expression:

\[T(1)=1, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=2T(n/2)+6n−1 \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=2 ;\quad b=2 ;\quad d=1; \\ & \text{We see that } 2 = 2^1 \text{ or } a = b^d \\ & \text{Therefore this is case 2 of the Master Theorem, we conclude: } \quad \\ & T(n) = O(nlog(n)) \\ \end{flalign*}\]

2. Given expression:

\[T(1)=2, \text{and for all } n≥2 \text{ a power of 3 }, T(n)=4T(n/3)+3n−5 \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=4 ;\quad b=3 ;\quad d=1; \\ & \text{We see that } 4 > 3^1 \text{ or } a > b^d \\ & \text{Therefore this is case 3 of the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^{\log_3 4}) \\ \end{flalign*}\]

3. Given expression:

\[T(1)=1, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=3T(n/2)+n^2−n \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=3 ;\quad b=2 ;\quad d=2; \\ & \text{We see that } 3 < 2^2 \text{ or } a < b^d \\ & \text{Therefore this is case 1 of the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^2) \\ \end{flalign*}\]

Exercise 3. Determine algorithm complexity:

1. Given expression:

\[T(1)=1, \text{and for all } n≥2, T(n)=3T(n-1)+2 \quad\]

1. Let \(T(n-1)=3 T(n-2)+2\)

   \[\begin{aligned} T(n)= & 3(3 T(n-2)+2)+2=3^2 T(n-2)+3 \cdot 2+2 \quad\\ &=3^2 T(n-2)+6+2=3^2 T(n-2)+8 \end{aligned}\]

2. Let \(T(n-2)=3 T(n-3)+2\)

   \[\begin{aligned} T(n)= & 3^2(3 T(n-3)+2)+8=3^3 T(n-3)+3^2 \cdot 2+8 \quad\\ & =3^3 T(n-3)+18+8=3^3 T(n-3)+26 \end{aligned}\]

3. Generalizing, let \(k\) be the number of steps:

   \[T(n)=3^k T(n-k)+2 \cdot\left(3^{k-1}+3^{k-2}+\ldots+1\right) \quad\]

The summation \(2 \cdot\left(3^{k-1}+3^{k-2}+\ldots+1\right)\) is a geometric series:

\[=2 \cdot \frac{3^k-1}{3-1}=2 \cdot \frac{3^k-1}{2}=3^k-1 \quad\]

Thus, \(T(n)=3^k T(n-k)+\left(3^k-1\right)\)

1. Let \(k=n-1\) :

   \[\begin{gathered} T(n)=3^{n-1} T(1)+\left(3^{n-1}-1\right)=3^{n-1} \cdot 1+\left(3^{n-1}-1\right) \quad \\ =3^{n-1}+3^{n-1}-1=2 \cdot 3^{n-1}-1 \end{gathered}\]

2. Final result:

   \[T(n)=2 \cdot 3^{n-1}-1\]

Thus, \(T(n)=O\left(3^n\right)\).

2. Given expression:

\[T(1)=3, \text{and for all } n≥2, T(n)=T(n-1)+2n−3 \quad\]

1. Let \(T(n-1)=T(n-2)+2(n-1)-3\)

   \[T(n)=T(n-2)+2(n-1)-3+2 n-3=T(n-2)+2 n-2 \quad\]

2. Let \(T(n-2)=T(n-3)+2(n-2)-3\)

   \[\begin{gathered} T(n)=T(n-3)+2(n-2)-3+2 n-2 \\ =T(n-3)+2 n-2+2(n-2)-3=T(n-3)+2 n-2+2 n-4-3=T(n-3)+4 n-9 \quad \end{gathered}\]

3. Generalizing:

   \[T(n)=T(n-k)+2 n-2+2(n-1)-3+2(n-2)-3+\ldots+2(n-k+1)-3 \quad\]

Let’s compute the contributions from the summation:

\[T(n)=T(n-k)+(2 n-2)+(2 n-4)+\ldots \quad\]

The series has \(k\) terms:

\[=T(n-k)+2 n \cdot k-3 k-2=T(n-k)+2 n k-3 k-2 \quad\]

1. Let \(k=n-1\) :

   \[\begin{gathered} T(n)=T(1)+2(n-1)(n-1)-3(n-1)-2 \\ =3+2(n-1)^2-3(n-1)-2 \\ =3+2\left(n^2-2 n+1\right)-3 n+3-2=2 n^2-7 n+4 \quad \end{gathered}\]

2. Final result:

   \[T(n)=2 n^2-7 n+4\]

Thus, \(T(n)=O\left(n^2\right)\).

3. Given expression:

\[T(1)=1, \text{and for all } n≥2, T(n)=2T(n-1)+n−1 \quad\]

1. Let \(T(n-1)=2 T(n-2)+(n-2)\)

   \[\begin{gathered} T(n)=2(2 T(n-2)+(n-2))+(n-1)=2^2 T(n-2)+2(n-2)+n-1 \quad \\ =2^2 T(n-2)+2 n-4+n-1=2^2 T(n-2)+3 n-5 \end{gathered}\]

2. Let \(T(n-2)=2 T(n-3)+(n-3)\)

   \[\begin{gathered} T(n)=2^2(2 T(n-3)+(n-3))+3 n-5 \\ =2^3 T(n-3)+2^2(n-3)+3 n-5=2^3 T(n-3)+4(n-3)+3 n-5 \quad\\ =2^3 T(n-3)+4 n-12+3 n-5=2^3 T(n-3)+7 n-17 \end{gathered}\]

3. Generalizing:

   \[T(n)=2^k T(n-k)+\sum_{j=0}^{k-1} 2^j \cdot(n-j-1) \quad\]

This simplifies to:

\[T(n)=2^k T(n-k)+(\text { a summation }) \quad\]

1. Let \(k=n-1\) :

   \[T(n)=2^{n-1} T(1)+\sum_{j=0}^{n-2} 2^j(n-j-1) \quad\]

The sum contributes:

\[=2^{n-1} \cdot 1+n\left(2^{n-1}-1\right)-\left(2^{n-1}-1\right)=2^{n-1}+n \cdot 2^{n-1}-2^{n-1}+1=(n-1) \cdot 2^{n-1}+1 \quad\]

1. Final result:

   \[T(n)=(n-1) \cdot 2^{n-1}+1\]

Thus, \(T(n)=O\left(2^n\right)\).

4. Given expression:

\[T(1)=5, \text{and for all } n≥2, T(n)=2T(n-1)+3n+1 \quad\]

1. Let \(T(n-1)=2 T(n-2)+3(n-1)+1\)

   \[\begin{gathered} T(n)=2(2 T(n-2)+3(n-1)+1)+3 n+1 \\ =2^2 T(n-2)+2(3(n-1)+1)+3 n+1=2^2 T(n-2)+6 n-6+2+3 n+1 \quad \\ =2^2 T(n-2)+9 n-3 \end{gathered}\]

2. Let \(T(n-2)=2 T(n-3)+3(n-2)+1\)

   \[\begin{gathered} T(n)=2^2(2 T(n-3)+3(n-2)+1)+9 n-3 \\ =2^3 T(n-3)+2^2(3(n-2)+1)+9 n-3 \\ =2^3 T(n-3)+12 n-24+4+9 n-3=2^3 T(n-3)+21 n-23 \quad \end{gathered}\]

3. Generalizing:

   \[T(n)=2^k T(n-k)+\sum_{j=0}^{k-1} 2^j(3(n-j)+1) \quad\]

4. Let \(k=n-1\) :

   \[T(n)=2^{n-1} T(1)+\sum_{j=0}^{n-2} 2^j(3(n-j)+1) \quad\]

Expanding the summation:

\[=2^{n-1} \cdot 5+\sum_{j=0}^{n-2}\left(3 n \cdot 2^j-3 j \cdot 2^j+2^j\right) \quad\]

1. Final result: Evaluating the terms yields:

   \[T(n)=5 \cdot 2^{n-1}+3 n\left(2^{n-1}-1\right)+\left(2^{n-1}-1\right)=5 \cdot 2^{n-1}+3 n \cdot 2^{n-1}-3 n+2^{n-1}-1 \quad\]

Simplifying,

\[=(5+3 n+1) 2^{n-1}-3 n-1=(3 n+6) 2^{n-1}-3 n-1 \quad\]

Thus, \(T(n)=O\left(2^n\right)\)

5. Given expression:

\[T(1)=4, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=2T(n/2)+3n+2 \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=2; \quad b=2; \quad d=1; \\ & \text{We see that } 2 = 2^1 \text{ or } a = b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n \log n) \\ \end{flalign*}\]

6. Given expression:

\[T(1)=1, \text{and for all } n≥2 \text{ a power of 6 }, T(n)=6T(n/6)+2n+3 \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=6; \quad b=6; \quad d=1; \\ & \text{We see that } 6 = 6^1 \text{ or } a = b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n \log n) \\ \end{flalign*}\]

7. Given expression:

\[T(1)=3, \text{and for all } n≥2 \text{ a power of 6 }, T(n)=6T(n/6)+3n−1 \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=6; \quad b=6; \quad d=1; \\ & \text{We see that } 6 = 6^1 \text{ or } a = b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n \log n) \\ \end{flalign*}\]

8. Given expression:

\[T(1)=3, \text{and for all } n≥2 \text{ a power of 3 }, T(n)=4T(n/3)+2n−1 \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=4; \quad b=3; \quad d=1; \\ & \text{We see that } 4 > 3^1 \text{ or } a > b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^{\log_3 4}) \\ \end{flalign*}\]

9. Given expression:

\[T(1)=4, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=3T(n/2)+n^2−2n+1 \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=3; \quad b=2; \quad d=2; \\ & \text{We see that } 3 < 2^2 \text{ or } a < b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^2) \\ \end{flalign*}\]

10. Given expression:

\[T(1)=1, \text{and for all } n≥2 \text{ a power of 2 }, T(n)=3T(n/2)+n−2 \quad\]

\[\begin{flalign*} & \text{Determine a, b, d: } \\ & a=3; \quad b=2; \quad d=1; \\ & \text{We see that } 3 > 2^1 \text{ or } a > b^d \\ & \text{By the Master Theorem, we conclude: } \quad \\ & T(n) = O(n^{\log_2 3}) \\ \end{flalign*}\]