单选题：Solving Recurrence
Consider the following pseudo-code.
strange($$a_1, \ldots, a_n$$):
$$1.\,\,$$if $$n \leq 2022$$ then return
$$2.\,\,$$strange($$a_{1}, \ldots, a_{\lfloor n/2 \rfloor}$$)
$$3.\,\,$$for $$i = 1$$ to $$n$$:
$$4.\quad$$for $$j = 1$$ to $$\lfloor \sqrt{n} \rfloor$$:
$$5.\quad\quad$$print($$a_i+a_j$$)
$$6.\,\,$$strange($$a_{\lfloor n/2 + 1 \rfloor}, \ldots, a_{n}$$)
What is the running time of this pseudo-code? Your answer should be as tight as possible. (You may assume that $$n$$ is a power of 2.)
A.$$O(n^{1.5})$$
B.$$O(n^{1.5})\log n$$
C.$$O(n^2)$$
D.None of the other options is correct
答案：A
strange($$a_1, \ldots, a_n$$):
$$1.\,\,$$if $$n \leq 2022$$ then return
$$2.\,\,$$strange($$a_{1}, \ldots, a_{\lfloor n/2 \rfloor}$$)
$$3.\,\,$$for $$i = 1$$ to $$n$$:
$$4.\quad$$for $$j = 1$$ to $$\lfloor \sqrt{n} \rfloor$$:
$$5.\quad\quad$$print($$a_i+a_j$$)
$$6.\,\,$$strange($$a_{\lfloor n/2 + 1 \rfloor}, \ldots, a_{n}$$)
What is the running time of this pseudo-code? Your answer should be as tight as possible. (You may assume that $$n$$ is a power of 2.)
A.$$O(n^{1.5})$$
B.$$O(n^{1.5})\log n$$
C.$$O(n^2)$$
D.None of the other options is correct
答案：A