题目内容

An algorithm has running time $T(n)$, which satisfies $T(n) = 4T(n/4) + O(n)$.So, its running time is _____.

A. $O(n\log n)$
B. $O(n)$
C. $O(n^2)$
D. $O(n^2\log n)$

查看答案

搜索结果不匹配？点我反馈

更多问题

If an algorithm has running time $T(n)= O(n\log n)$, then $T(n)$ may most likely satisfy that _____.

A. $T(n) = 4T(n/4) + O(n^2)$
B. $T(n) = 4T(n/4) + O(n) $
C. $T(n) = 3T(n/2)+O(n) $
D. $T(n) = 2T(n/2) + O(\log n)$

Under the same condition as exercise 3.Then, there is not a minimum spanning tree of [mathjaxinline]G[/mathjaxinline] that doesn’t contain the edge [mathjaxinline]e[/mathjaxinline].

Assume that each of the following sets are not equal. Which one is the biggest set?

A. P
B. NP
C. co-NP
D. EXP

If we have a magic machine that can solve 3-SAT problem in unit time. Which of the following problem can NOT be solve if we only use this machine polynomial times? (Assume P ≠ NP)

A. INDEPENDENT-SET
B. VERTEX-COVER
C. PRIMES
D. HALTING PROBLEM