1
vote
2answers
41 views

How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$ For the first, I don't have a formal proof but I ...
1
vote
2answers
29 views

math rules when having 2 variables in Big-O

I came across the following in some lecture notes: O(log n) + O(log m) = O(log n + log m ) = O(log (m + n)) that last step to ...
1
vote
1answer
31 views

How on earth will anyone prove $n^3-3n^2+n-1=Θ(n^3)$

I know its homework question.Sorry for that.But i was solving all problems of Skiena and chapter and got stuck to this problem of 2nd chapter 2.10. Its easy to prove $n^3-3n^2+n-1=O(n^3)$ because ...
0
votes
1answer
24 views

What is the time complexity of an $O((\ln n)^{\ln n})$ algorithm?

How can the time complexity of an $O((\ln n)^{\ln n})$ algorithm be simplified and compared to some other time complexities?
-2
votes
1answer
47 views

Prove that $\log n = O(\log^2 n)$

Trying to solve this, but I can't seem to figure it out. Its fairly straight forward.
2
votes
0answers
38 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
1
vote
1answer
31 views

How do you define computational complexity abstractly?

Let the problem we're studying be $f : X \to Y$. Say, I don't know what I want to define time-complexity with respect to, I just know I have a map $|\cdot| : X \to \Bbb{R}$, such that $|\cdot| \geq ...
0
votes
0answers
15 views

How to determine sub-exponential time growth?

I'm a little bit confused of sub-exponential time growth; consider the definition from Hoffstein's book An Introduction to Mathematical Cryptography: Given input of $k$ bits, then if an algorithm ...
0
votes
1answer
31 views

Order functions by speed of their asymptotic growths

We are given list of functions. Task is to sort it by the speed of their asumptotic growth in ascending order. Yes, it's a homework. I already spent some solid amount of time calculating limits. I ...
1
vote
0answers
49 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
0
votes
0answers
26 views

Why $17T(n/16) + n \log n$ satisfies the case 2 of the Master Theorem?

Using the Master Theorem, we have that $17T(n/16) + n \log n$ is $\theta(n^{log_{16}17} log^2 n)$ My question is, why $n \log n = \theta(n^{\log_{16}17} \log^1 n)$, being $\log_{16}17$ approximately ...
3
votes
2answers
76 views

Big O/little o true/false

These are all from Sipser's book, second edition. I was just hoping someone could verify/explain those that are more difficult for me. $2n = O(n)$: true $n^2 = O(n)$: false $n^2 = O(n\log^2 n)$: I ...
2
votes
1answer
60 views

From programming to mathematics

I'm studying algorithms design and analysis, but there is a code that I can't understand. I know that: Let $\mathcal P$ be the main program, and $\mathcal P \in O\left(\varphi(n)\right)$ with ...
0
votes
2answers
32 views

Sum of a sum [algorithm design and analysis]

I'm studying the algorithm analysis of one piece of code, and I have to find the big-O notation of the sum of a sum. ...
0
votes
1answer
80 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
0
votes
1answer
19 views

BigOh - How to determine the upper bound dealing with eccentric series?

I would like to know what is the way to determine the upper bound of a series in BigOh terms. For example, suppose the following series is given: 2 + 6 + 10 + 14 + ..... + ((4 * n) - 2) How can I ...
-5
votes
3answers
72 views

Big O notations and asymtotic analysis [closed]

Kindly answer and explain it to me too. this is how i solved
0
votes
2answers
134 views

The result of O(f(n)) - O(f(n))

My question is in the field of the big-O-notation and complexity/asymptotic functions: Probably something that I'm missing, but I've couldn't find any well explained solution for the following: What ...
1
vote
2answers
138 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
1
vote
1answer
38 views

Calculating algorithmic complexity

Given the following bit of code, how would I calculate the complexity? ...
1
vote
3answers
281 views

Big O notation - Proving that a function is not O(n)

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$. I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$. Many ...
2
votes
3answers
74 views

Determine appropriate $c$ and $x_0$ for Big-O proofs.

"Prove that $f(x)$ is $O(x^2)$:" $$f(x) = \frac{x^4+2x-7}{2x^2-x-1}$$ Let $c=10$ (addition of coefficients of the numerator less the addition of coefficients of the denominator), and $x_0 = 1$ (the ...
1
vote
1answer
28 views

Correctness of complexity analysis of recursive algorithm

Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?
1
vote
0answers
42 views

Computational Complexity

My question is very basic, it is just so that I have a basic grasp of the terminology of algorithm speed. When someone says an algorithm speed is $O(n^2)$ they say that the number of steps of this ...
1
vote
3answers
41 views

I have an answer for an asymptotic analysis, which i cannot accept. please explain me where i go wrong.

We have the following function definitions: \begin{align*}f_1 (n) &= n^{n^{\frac{1}{2}}} \\ f_2 (n) &= 2^n \\ f_3 (n) &= n^{10} 2^{\frac{n}{2}} \\ f_4 (n) &= \sum_{i=1}^{n} (i+1) ...
-2
votes
2answers
71 views

How prove big O notation?

How to prove this function 1). $f(n)=n^3 − 5n^2 + 25n - 165$ is $O(n^3)$. 2)$3+\sin(1/n)$
0
votes
1answer
58 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
1
vote
1answer
32 views

Is $O(n \log n)$ always smaller than $O (m)$ for $n-1 < m < n^2$?

I am writing an algorithm that needs to finish in $O(m)$. The problem is for a graph $G( V, E )$, where $m = |E|$ and $n = |V|$. $m$ can be in the range of $n-1$ to $n^2 - 1$. If I do some ...
0
votes
1answer
28 views

Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
0
votes
2answers
41 views

What does $\text{poly}$ stand for in $O(\log^{10.5}n \cdot \text{poly}(\log \log n))$?

I posted this question on cstheory and found that "poly(f(n))" is shorthand for "polynomial in f(n)" or $f(n)^{O(1)}$, hence poly(log log n) is shorthand for $(log log n)^{O(1)}$. However, I don't ...
0
votes
0answers
92 views

In this insertion sort algorithm for example, how would I prove the algorithm's time complexity is O(n^2)?

Take the following insertion sort algorithm: I know it's O(n^2) fairly easy by examining it. But as far as proving it's O(n^2), how would I go about doing that? I could add up all the operations, ...
1
vote
1answer
68 views

What is the difference between $O(N/ \log_2(N))$ and $N-o(N)$?

On the second page of this paper under the introduction section they say "We first show that for the set of parameters considered by [16], the function family has $O(N/ \log_2(N))$ simultaneously ...
0
votes
2answers
80 views

For $f(n) = \log n$ and $g(n) = n^c$, where $0 < c < 1$, is it always true that $f$ is $O(g)$?

In complexity analysis, basic functions you encounter are functions like $f_1(n) = \log n$, $f_2(n) = n^2$ and $f_3(n) = n^3$. It is fairly obvious to me that $f_1$ is $O(f_2)$ and $O(f_3)$, but it is ...
3
votes
1answer
2k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
3
votes
5answers
353 views

Provide an algorithm $O (n ^ 3 \log n)$, any example?

Provide an algorithm computing performance $O (n^3 \log n)$. Your algorithm should contain only simple operations. Any idea of how to approach this problem?...I am studying for the computer science ...
3
votes
1answer
135 views

Using the definition of big-oh notation, show that for any $k,\gamma>1$, $n^k=O(\gamma^n)$.

This question had been on my midterm in a course I took last year: Prove that for any $k,\gamma>1$, $n^k=O(\gamma^n)$. Intuitively, this makes sense. Even the fastest exponential algorithm ...
0
votes
1answer
42 views

Complexity of Code Snippet Without Knowing A Function?

I have the code snippet: int const n = 300; int nArr[n]; for(int i = 0; i<n; i++) { if(i >x) copyPrevious(nArr,i); } I need to find the complexity ...
0
votes
4answers
1k views

Big-O: Prove $2^n$ is $O(n!)$ [duplicate]

I am a little stuck trying to prove that $2^n$ is $O(n!)$. Obviously, I can tell in a few ways that this is the case. For one, based on Big-$O$ hierarchy, the exponential is beneath the factorial in ...
6
votes
1answer
91 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
35 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
88 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
727 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
43 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
57 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
33 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
117 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
29 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
296 views

Big Theta Expression Question

I need help - I have to express this function: $f(n)=15n \log n + 12n + 9 \log n +25$ in terms of big theta notation. I believe that it is $\Theta(n \log n)$, but I have to prove it mathematically. ...
1
vote
1answer
80 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 ...