Tagged Questions
1
vote
2answers
102 views
Möbius function help
Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate ...
0
votes
2answers
35 views
How can we denote the following function in terms of big-O notation?
I have got a function and want to denote it in terms of bigO notation.
f(n) = log4n+n*(1/3). Is this function O(n)? (* here is the multiplication) Thanks for your help
1
vote
2answers
34 views
The growth rate of the functions with respect to each other
There are two functions , for example $f(n)=3\sqrt{n}$, and $g(n)=\log n$. Which one dominates, in other words, is $f(n)=O(g(n))$ or $f(n)= \Omega(g(n))$?
Thank you.
0
votes
2answers
46 views
For what $f(n)$ does $O(f(n) \log n)=O(\log\log n)$?
$k=f(n)$.
Given $O(k \log_2 n)$, what function $f$ of $n$ would be needed for it to equal $O(\log_2 \log_2 n)$?
(where $k \in n \in \mathbb{Z}^+$)
1
vote
0answers
10 views
On the computational complexity of plugging in numbers into general expressions to obtain special ones
There are many expressions, which can be considered straight generalizations of others.
I'm motivated by values of integral expressions specifically, for example there is
$$\int_0^\infty e^{-a ...
1
vote
3answers
43 views
Computational complexity proof
I would like to know how to prove the following:
$2^n \in O(n!)$
I know that I have to show that for a constant C, we have $2^n \leq C*n!$
Right?
