Cho biết độ phức tạp của đoạn mã giả sau dùng ký hiệu big-O.s = 0for (i = 1; i <= n; i *= 3)s = s + a[i]a.O( n )b.O(n^2)c.O(logn)d.O(nlogn)Clear my choice

1. Break Down the Problem

We need to analyze the pseudocode provided to determine its time complexity using Big-O notation. The pseudocode is structured as follows:

s = 0
for (i = 1; i <= n; i *= 3)
    s = s + a[i]

2. Relevant Concepts

The time complexity of a loop can be analyzed by examining how the loop variable changes over each iteration and how many times the loop will execute in relation to the input size $n$.

3. Analysis and Detail

• The loop starts with $i = 1$.
• In each iteration, $i$ is multiplied by 3 (i *= 3).
• The loop continues until $i$ exceeds $n$.

To find out how many iterations the loop runs, we can express $i$ in terms of $n$:

1. In the first iteration: $i = 1$
2. In the second iteration: $i = 3$
3. In the third iteration: $i = 3^2 = 9$
4. In the fourth iteration: $i = 3^3 = 27$
5. And so on...

We need to determine when $i$ becomes greater than $n$:

$3^k \leq n$

Taking the logarithm base 3 of both sides, we get:

$k \leq \log_3(n)$

Thus, the number of iterations $k$ can be approximated by:

$k \approx O(\log_3(n)) = O(\log(n))$

4. Verify and Summarize

The loop runs logarithmically with respect to $n$ since it increases in powers of 3. Therefore, the time complexity of this pseudocode is $O(\log n)$.

Final Answer

The time complexity of the given pseudocode is c. O(log n).