# Tagged Questions

31 views

### How do I prove that $a = n/2$ is a tight upper bound for the recurrence relation $T(n) = T(n-a) + T(a) + n$?

I have a recurrence relation: $$T(n) = T(n-a) + T(a) + n$$ which happens to be $O(n^2)$ complexity. How do I now prove that: $$a = n/2$$ is a tight upper bound for this relation? I have been ...
42 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 ...
30 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 ...
32 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 ...
27 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?
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.
39 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 ...
31 views

28 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 ...
81 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 ...
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 ...
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. ...
87 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 ...
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 ...
74 views

### Big O notations and asymtotic analysis [closed]

Kindly answer and explain it to me too. this is how i solved
135 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 ...
152 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 ...
40 views

### Calculating algorithmic complexity

Given the following bit of code, how would I calculate the complexity? ...
318 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 ...
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 ...
29 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)?
44 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 ...
43 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) ...
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)$
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 ...
33 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 ...
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 ...
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 ...
103 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, ...
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 ...
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 ...
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 ...
359 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 ...
136 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 ...
53 views

...
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 ...
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 ...
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 ...
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 ...