1
vote
1answer
12 views

Find functions which change asymptotic properties if raised to 2

Kindly give an example of positive functions f(n) and g(n) such that f(n) = O(g(n)) but it does not hold that 2^f(n) = O(2^g(n)). A friend asked this question as this came in one of his ...
0
votes
0answers
25 views

Help with understand the growth order of functions

I am taking an Algorithms class and I understand everything that relates to the asymptotic growth and Order of growth for a given function (Theta, Omega, etc). However, I am having trouble in ...
4
votes
0answers
72 views

How to efficiently calculate $ax+b$ once I know $a$ and $b$?

What's the cheapest way to calculate $ax+b$ several times once I know the values for $a$ and $b$? For instance, the cheapest way to calculate $a+b+x$ several times once I know the values for $a$ and ...
0
votes
1answer
31 views

Is there a way to compute if(i < j) k := (a + b)c with polynomials over $\Bbb{Z}_p$?

Let $p$ be a prime and let all variables be in $\Bbb{Z}_p$. Then you can write the result of if(i > 0) k = (a + b)c; (C code) as a polynomial $k := ...
0
votes
0answers
154 views

Prove that div(x,y) is primitive recursive (integer division

Prove that div(x,y) is primitive recursive (integer division). I tried thinking about it, I just don't know how to write it formally. it is kinda obvious that I should subtract y from x several times ...
4
votes
3answers
427 views

Growth rate of $n^{\sin n}$

Is there a way of comparing the growth of functions $ f(n) = n ^ {\sin(n)} $ and $ g(n) = n ^ {1/2} $ in terms of $ O, o, \Omega, \omega, \Theta $ ? Periodically, $ f(n) $ keeps going above and ...
0
votes
2answers
71 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
44 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
56 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
2answers
130 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 ...
1
vote
0answers
14 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
46 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?