3
votes
Accepted
Linear time approximate multiplication
If you just want a $\Theta(ab)$ precision then we can just consider the binary representation of $a, b$, and we can easily get two "ceiling" power of 2:
$$
a' = \min \{ 2^w | 2^w \ge a\} \\
...
- 68
2
votes
Must an algorithm terminate to be in NPTIME?
Remember, NP is capturing the idea that you can check a solution in polynomial time. So in this case, if you are given a number, you can easily verify if it is a nontrivial factor of your input or not....
- 308
2
votes
Accepted
Does log(log(n)) grow asymptotically slower than log(n) / log(log(n))?
Let $k=\log n$, so we are considering $\log k$ and $k/\log k$. We just need to calculate a simple limitation $$\lim_{k\rightarrow\infty}\frac{\log k}{k/\log k}.$$ If the limitation is $0$ then $\log k=...
- 511
1
vote
Must an algorithm terminate to be in NPTIME?
A proper definition of $\mathsf{NP}$ (or $\mathsf{NPTIME}$, as you seem to call it) should have been given in your course. You need to check the definition to see whether it requires all branches of ...
- 2,231
1
vote
Accepted
What is the time complexity of determine_build_order function below?
Yes, your analysis is mostly a correct. The while loop takes ( O(E) ) time because the for loop inside processes each edge ...
- 26
Only top scored, non community-wiki answers of a minimum length are eligible