Tagged Questions

5
votes
1answer
85 views

Simplify $O(n^k/2^n)$

In one of my complexity analysis, I came up with $O(n^k/2^n)$, where $k$ is a fixed number and $n$ is the size of the data. However I rarely see a big-O written as this. Is there a way to even further ...
0
votes
0answers
18 views

Complexity of index calculus method

I read somewhere that complexity of index calculus method which calculates discrete logarithm over $Z_p^*$ is $O\left(e^{(1 + o(1))(\sqrt{ln(p)\times ln(ln(p))}\;)}\right)$. My question is, why ...
1
vote
1answer
33 views

Big $\mathcal{O}$ notation for multiple parameters?

The following is an excerpt from CLRS: $\mathcal{O}(g(n,m)) = \{ f(n,m): \text{there exist positive constants }c, n_0,\text{ and } m_0\text{ such that }0 \le f(n,m) \le cg(n,m)\text{ for all }n ...
1
vote
1answer
46 views

What does it mean for a function to be polynomially bounded

There is a definition in my notes and says, When functions are polynomially bounded, the initial conditions (the value on small inputs) do not make a difference for the solution in ...
1
vote
2answers
32 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.
1
vote
0answers
42 views

Asymptotic notation of the following function

I have two functions, $f(n)$ and $g(n)$, and I am trying to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$. I am not sure about my answers. Help will be appreciated. a) ...
3
votes
1answer
22 views

Indicating the complexity of functions

I am not sure about my answer about the following question. Can anyone help? I try to express whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$, where $f(n)=n^{0,1234}$ and ...
1
vote
1answer
47 views

Difficulty proving / disproving the following equalities relations ( Big Ω)

I have left with some functions I can't find witenesses for proving/disproving Big Ω equalities relations. Here are the three relations: $ \sum\limits_{i=1}^{n} (i^3 - i ^2) = \Omega(n^4) $ ...
1
vote
0answers
22 views

Evaluating a simple sum bound

I'm trying to evaluate and prove a simple statement but It seems really raw/bad solution. I would like to advise with you if this is the right way because It is really getting more complicated than It ...
1
vote
1answer
56 views

Help finding Complexity in Big-O notation

I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or prove that it's bounded by $n^3$ or $n^4$. Can I use triple ...
2
votes
1answer
83 views

Does $\Theta(m \log n)$ and $0 < m < n^2$ imply $\Theta(n^2 \log n)$?

If we have an algorithm with complexity $\Theta(m + n^2)$ and we know that $0 < m < n^2$ then its complexity becomes $\Theta(n^2)$. But if we had an algorithm with complexity $\Theta(m\log{n})$ ...
1
vote
0answers
69 views

“Balancing” two infinities

Given these two computational complexities of 2 algorithms (factoring): $\exp(O(\sqrt{\log n \log \log n}))$ $O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$ where I imagine the first one goes to ...
4
votes
2answers
176 views

Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
0
votes
0answers
118 views

Solve recursion formula using Recursion Tree concept

I'm trying to figure out an important idea regarding solving Regression formulas / Recurrsion formulas using the Recursion Tree idea. I will first write down the exercise and then I'll try to explain ...
0
votes
1answer
64 views

Prove that the little-o definition doesn't hold for two function (f and g)

I need your help with the following statement: Show there exist two function $f(n), g(n)$ such that meet the following definition: $g(n) = O(f(n))$ and $f(n) \ne O(g(n))$ But don't meet the ...
0
votes
2answers
83 views

Some Big-O complexity definition proofs

I'm trying to prove (by definition) the following but to no avail: $n^{n/2} \ne O(3^{n/2}) $ $n! \ne O(3^n)$ $(n-b)^a = \Theta(n^a)$ $a,b $ are both constants whereas $a > 0 $ and $b$ ...
0
votes
2answers
189 views

Little-o proof by definition

I'm trying to figure out how to prove the following but to no avail. Given the following functions : $f(n) = n^3 -4n$ $g(n) = 5n^2 + 3n$ I have to show that $g(n) = o(f(n))$ by definition, that ...
1
vote
3answers
91 views

Order of magnitudes comparasions

I have a list of order of magnitudes I want to compare. My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation. I need your help with the following. I ...
0
votes
3answers
58 views

Big-O compared to a new Operator

I'm trying to figure out a new operator compared to the Big O. Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ ...
1
vote
1answer
114 views

Orders of Growth between Polynomial and Exponential

What is known in contemporary mathematics about orders of growth for functions that exceed any degree polynomial, but fall short of exponential? This is a subject for which I've found little ...
0
votes
2answers
47 views

Find the rate of growth for $\sum_{n=1}^N 1/n^p$ in term of big $O$ notation

Find the rate of growth for $$ \sum_{n=1}^N \frac{1}{n^p} $$ in term of big $O$ notation for the three cases $0 < p < 1$, $p=1$ and $p>1$. It seems the question can be approached by ...
0
votes
3answers
109 views

O-notation property - sum of the first n powers growth

I read here that in the tenth property: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/latex/complexity.pdf The sum of the first $nr^{th}$ powers grows as the $(r+1)^{th}$ power This is not very ...
1
vote
1answer
280 views

Big-O notation always holds for this two functions?

For two any functions $f(n)$ and $g(n)$ always holds: $f(n) = O(g(n))$ or $g(n) = O(f(n))$ Right? Thanks
1
vote
2answers
57 views

Simplifying a logarithm of a little-o (circuit complexity)

I have an expression which I think is $o(2^n)$, but I'm having difficulty simplifying it: $o(2^n/n)\log(o(2^n/n) + n)$ I can ignore the extra $n$ sitting at the end, since $o(2^n/n) + n = o(2^n/n + ...
0
votes
0answers
56 views

Question about an asymptotic analysis proof in Ball Collision Decoding paper.

On page 21 of Daniel Bernstein's paper "Smaller decoding exponents: ball-collision decoding" he presents a proof that I have a few questions about. $P,Q,R,L$ and $W$ are all positive and close to ...
2
votes
2answers
611 views

Help proving that $(n+a)^b = \Theta(n^b)$

Please you apologize me by my English. I don't know how make that: $$(n+a)^b = \Theta(n^b), b > 0$$ I know, I must to find two constants such that: $$ c_{1} n^b \leq (n+a)^b \leq c_{2} n^b $$ I ...
0
votes
0answers
98 views

Asymptotic equality

How can i prove this asymptotic equation? $$2n^n + 2n^{n+1} = 2n^n + \Theta(2^n) $$ The theorem says: $$ \Theta(g(n)) = \{f(n): \exists c_1, c_2, n_0 > 0\,\, c_1g(n) \le f(n) \le c_2g(n), \,\,n ...
3
votes
2answers
77 views

Is it possible to prove that a problem $P$ is decidable in $O(\phi)$ without providing an algorithm that decides $P$ in $O(\phi)$?

Phrased another way: Are there any problems that are known to be decidable in a better worst-case time complexity than the best known procedure?
0
votes
1answer
296 views

What is the computational complexity of a brute force perfect numbers finder algorithm?

A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking ...
2
votes
0answers
41 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
0
votes
2answers
66 views

Running times comparison

I am trying to find which of following algorithms has the smallest running time: 1) $O\left(\sqrt{q}\cdot\operatorname{polylog}(q)\right)$; is that linearithmic? 2) ...
2
votes
1answer
366 views

Prove the following: if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(h(n))$ then $f(n)$ is $O(h(n))$

I understand that $f(n) \leq Ng(n)$ and $g(n) \leq Nh(n)$ so obviously $f(n) \leq Nh(n)$, but how would one go about proving this using proper semantics (using big $O$ notation)?
0
votes
1answer
190 views

Finding a Big-O notation of: $\sum\limits_{i=1}^{k} ( t(a_i n)) + n$

I'm trying to find a Big-O notation of: $\displaystyle\sum_{i=1}^{k} ( t(a_in)) + n$, where $\displaystyle\sum_{i=1}^{k} (a_i) < 1$ using a recursion tree method and substitution method. I've ...
0
votes
3answers
176 views

Using $O(n)$ to determine limits of form $1^{\infty},\frac{0}{0},0\times\infty,{\infty}^0,0^0$?

Is it sufficient to use $O(n)$ repeatedly on $1^{\infty},\frac{0}{0},0\times\infty,{\infty}^0,0^0$ to get determinate forms? For example if we look at $\frac{0}{0}$ then $$\frac{O(f(n))}{O(g(n))}$$ ...
2
votes
2answers
206 views

Solving recurrences of the form $T(n) = aT(n/a) + \Theta(n \log_2 a)$

The time complexity for the merge sort algorithm is $T(n) = 2T(n/2)+\Theta(n)$, and the solution to this recurrence is $\Theta(n\lg n)$. However; assume you are not dividing the array in half for ...