What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]**2 for j in range(n): A[j] = A[i]/5

Question

BlackTom AI · Accepted Answer

Each outer iteration executes a constant-time square and then a full inner loop of n assignments, so the overall growth is quadratic.

1) Relevant concepts
- Time complexity counts how the number of basic operations grows with input size n.
- Nested loops typically multiply their iteration counts: an outer loop of n and an inner loop of n give O(n * n) = O(n^2).
- Constant-time operations (like a single assignment or arithmetic) do not change the asymptotic class.

2) Step-by-step reasoning
- The code sets n = np.size(A). Even though the snippet shows A initialized with 5, complexity analysis treats n as the variable input size.
- The outer loop: for i in range(n):
    - A[i] = A[i]**2  — one constant-time operation per i.
    - The inner loop: for j in range(n): A[j] = A[i]/5 — runs n times for each i, each iteration is a constant-time assignment.
- So for each i, work done = 1 (square) + n (inner assignments) = n + 1 operations.

3) Intermediate calculations
- Total operations T(n) = sum_{i=1..n} (n + 1) = n * (n + 1) = n^2 + n.
- As n grows, the dominant term is n^2, so T(n) = Theta(n^2).

4) Why this answer is correct
- The presence of an inner loop nested inside the outer loop multiplies the iteration counts, producing quadratic growth. Constant-time work per inner iteration does not change the asymptotic result.

5) Why the other options are incorrect
- a. O(n): would be correct only if the two loops were sequential (one after the other) or if the inner loop did not depend on the outer loop; here the inner loop is nested, so it's not O(n).
- c. O(n^3): would require three nested loops or an extra factor of n; we only have two nested loops.
- d. O(n log n): arises from algorithms like efficient sorting or divide-and-conquer with logarithmic factors; not applicable here.

Conclusion: The time complexity is O(n^2), so the correct choice is b. O(n^2).

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]**2 for j in range(n): A[j] = A[i]/5单项选择题

类似问题

What is the big-O of the worst-case time cost of inserting an element somewhere into an array of size n? Select the tightest bound that holds.

Which of the following is a big-O description that applies to the function g(n) = 18log n + 2n + 3n log n? Select the tightest bound that holds.

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]2 print(A) for j in range(i,n): for k in range(i,j): A[j] = A[i]/5 for i in range(n): print(A) A[i] = A[i]2 for j in range(i, n): A[j] = A[i]/5

What is the time complexity of the following Python code? A = np.zeros(5) n = np.size(A) for i in range(n): A[i] = A[i]**2 for j in range(i, n): A[j] = A[i]/5 print(A)

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单