0
votes
1answer
26 views

compare n^log log n with c^n and n^k

What is the relation in terms of asymptotic analysis, between n^log log n and $c^n$,$n^k$ ? how can find relation between such functions?
2
votes
1answer
44 views

Big Oh and Big Theta relations confirmation

I just want to confirm these statements, I know that Big O, and Big theta, are partial order and equivalence relations respectively, all positive integers, but not sure on these restrictions. $f:N ...
-1
votes
0answers
63 views

Sorting functions by their orders of magnitude

I have ordered the list to what I believe to be correct: $n!$, $2\times 3^n$, $3\times2^n$, $n^2$, $n\log n$ + $\sqrt{n}$, $n$ $F\prec G$ means that $F\in \mathcal{O}(G)$ but $F \not\in \Theta(G)$ ...
1
vote
2answers
105 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 ...
2
votes
2answers
74 views

Is it true that $(2^n+n^2)(n^3+3^n)$ is $O(6^n)$?

$(2^n+n^2)$ is $O(2^n)$ and $(n^3+3^n)$ is $O(3^n)$, therefore I conclude that $(2^n+n^2)(n^3+3^n)$ is $O(2^n*3^n)=O(6^n)$
0
votes
1answer
48 views

How to prove statement about $\mathcal{O}, \Theta$ and $\hbox{o}$?

For a given function g, Prove that $\hbox{o}(g) \neq O(g) - Θ(g)$. Thanks for the help in advance
3
votes
1answer
25 views

Analyzing $n_{i+1} = n_i - n_i^{3/4}$

I have a non-linear recurrence given by $$n_0 = N \\ n_{i+1} = n_i - n_i^{3/4}$$ Are there any techniques to solve this for an exact closed form? Or in lieu of that, an asymptotic estimation? I'm ...
2
votes
2answers
88 views

Understanding definition of big-O notation

In a textbook, I came across a definition of big-oh notation, it goes as follows: We say that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $$|f(x)| \le C|g(x)|$$ whenever $x \gt ...
15
votes
4answers
585 views

Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
-2
votes
2answers
61 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)$
4
votes
1answer
87 views

Finding a tight upperbound

A call graph $G = \{V,E\}$ on phone metadata has a vertex $v \in V$ for each phone number and an edge $\{v,w\} \in E$ if there has been a phone call between $v$ and $w$. One can monitor calls of a set ...
1
vote
1answer
24 views

Big O notation question of Kolman's book

If $$f(x) = x^{100} , g(x) = 2^x. $$ Show that $f(x)$ is a big $O(g(x))$, but $g(x)$ is not big $O(f(x))$.
1
vote
1answer
62 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
0
votes
1answer
33 views

Asymptotic equality proof with $a_n^2 \ln a_n ~ n$

Given $a_n^2 \ln a_n \sim n$, prove that $a_n \sim \sqrt{\frac{2n}{\ln n}}$. How do I approach this?
1
vote
0answers
51 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
3
votes
1answer
106 views

Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$

Find the constant $c$ in the equation $$\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$$ I've tried to use this asymptotics $$C_n^k \sim \frac{n^m}{m!} \sim e^{m\ln n ...
0
votes
1answer
55 views

Given $ h(x)=f(x)+O(g(x)) $ estimate using asymptotic notation $\frac{1}{h(x)}$

Given $ h(x)=f(x)+O(g(x)) $ and knowing that $ \lim_{x \to \infty}=\frac{g(x)}{f(x)}=0$ (int other words $f(x)=o(g(x))$) find such F(x) and G(x), $\frac{1}{h(x)}=F(x)+O(G(x)) $. Because $ ...
2
votes
2answers
154 views

Big O and Omega Properties

I am trying to think of a case where this is not true: $f(n) = O(g(n))$ and $f(n) \neq \Omega(g(n))$, does $f(n) = o(g(n))$? I suspect that it has to do with the varying $c$ and $n_{0}$ constants ...
0
votes
1answer
54 views

Time Complexity involving a conditional f(n) when n is even and odd

Trying to find an asymptotic relationship between: $f(n)$ and $n^2$ where $f(n)$: if n is even, $f(n) = 8n$. if n is odd, $f(n) = 5.5n^2$. Not sure how to approach when the function is ...
2
votes
1answer
53 views

Comparing time complexities

I'm trying to understand which of the following functions is strictly faster growing ($\Omega$, $o$-notation or $\theta$-notation). Not sure how to approach the following equations: $$\bf{n^{0.3} \ ...
0
votes
2answers
380 views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
0
votes
1answer
41 views

Comparing algorithm running times expressed in complex form

I know how to compare running times of different algorithms. Sometimes it is obvious, sometimes it requires simplifications, and sometimes dividing and using L'Hopital's rule to see if it converges ...
0
votes
1answer
90 views

Big O, Big Omega - getting this problem wrong, need understanding

I'm not sure I understand what to do here. Will someone help me understand how to determine what these recurrence relations are Big-O or Big-Omega of? Problem $a_0 = 0$ and $a_n = 1 + a_{n-1}$ ...
5
votes
1answer
152 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
1
vote
2answers
280 views

Figuring out which functions are Big-O of other functions (of a of 9 different functions). Where do I start?

Problem I need to arrange the following functions in order, so that each function is big-oh of the next function. Functions Attempt @ Solution Understanding: I don't understand what to do here. ...
2
votes
3answers
282 views

Big $\Omega$ question! Prove $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$

Problem Prove $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$. Attempt @ Solution $f(n) = n^3(1-6/n+11/n^2-6/n^3)$ $g(n) = n^3$ Show that there exists a $C > 0$ and $n_0$ such that $f(n) \ge Cg(n)$ for all ...
4
votes
4answers
118 views

Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$

Problem Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$ Attempt at Solution $f(n) = (n+1)(n+2)(n+3)$ $g(n) = n^3$ Show that there exists an $n_0$ and $C > 0$ such that $f(n) \le Cg(n)$ whenever $n ...
0
votes
1answer
94 views

Some discrete math questions, Big-O, Big-Omega, Asymptotics, etc.

I don't understand how to prove: $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$. Also, what am I supposed to do here? For each of the following predicates, determine, if possible, the smallest positive ...
0
votes
4answers
103 views

Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$. (Big-o notation) [closed]

Will someone help me prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$? Thank you.
0
votes
1answer
139 views

How to find $n^2 - 2n - 3$ is $\Omega(n^2)$?

How can I show that $n^2 - 2n - 3$ is $\Omega(n^2)$?
1
vote
4answers
140 views

I feel very stupid. Will someone walk me through a step-by-step in plain english of this Big-O problem?

Prove that $n^2 + 2n + 3$ is $O(n^2)$. Find values for $C$ and $k$ that prove that they work. Edit: In particular, I don't at all understand how to find C and k. I asked a similar question but ...
4
votes
5answers
2k views

Big-O Notation - Prove that $n^2 + 2n + 3$ is $\mathcal O(n^2)$

I'm taking a course in Discrete Mathematics this summer, and my book doesn't offer a very good explanation of Big-O notation. I understand that if $f(x)$ is $\mathcal O(g(x))$ it means that there ...
23
votes
0answers
476 views

On the number of complete and gap-free compositions

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
4
votes
4answers
202 views

Determine whether $F(x)= 5x+10$ is $O(x^2)$

Please, can someone here help me to understand the Big-O notation in discrete mathematics? Determine whether $F(x)= 5x+10$ is $O(x^2)$
2
votes
0answers
47 views

Solving $B(n)=3B(\frac{n}{\log_{2}n}) +n$ using master theorem.

First of all sorry if this has been posted before, I found lots of master theorem questions on the search but not one like this. I am familiar with master theorem but a little uncomfortable with ...
3
votes
1answer
62 views

$ (n-7)^2$ is $\Theta(n^2) $ Prove if it's true

$$ (n-7)^2 \, \text{is} \, \Theta(n^2) $$ Is this correct? So far I have: $ (n-7)^2 \, \text{is} \, O(n^2) \\ n^2 -14n +49 \, \text{is} \, O(n^2) \\ \begin{align} n^2 -14n +49 & \le \, C ...
0
votes
1answer
85 views

Big-O Big theta Big omega papers

I'm studying algorithms complexities by myself (my university didn't it to me) and I'd love if someone could help me in finding good resources to learn fundamental algorithms complexities proofing. ...
1
vote
1answer
138 views

Where can I learn about solving Big-Oh problems that are written in algebra? [duplicate]

Where can I learn about solving Big-Oh problems that are written in algebra? Such as this $$\sum_{i=1}^{n} (3i + 2n) = O(n^2)$$
3
votes
1answer
294 views

Proving a function is big O

How would I go about proving a function is big O? Do I use the regular proofs (direct, contrapositive, contradiction)? Example: Prove that $x^n$ is $O(n!)$ for every real number $x$. My proof by ...
1
vote
1answer
114 views

How do we show that $x^5y^3 + x^4y^4 + x^3y^5$ is $\Omega(x^3y^3)$

Basically I'm wondering how I can show that $x^5y^3 + x^4y^4 + x^3y^5$ is $\Omega(x^3y^3)$. Any ideas? Thanks a lot!
0
votes
1answer
238 views

If $f(n) = \Theta (g(n))$, why does $g(n) = \Omega (f(n))$?

Why is this the case? I understand that if $f(n) = \Theta (g(n))$ then $c_1g(n)<f(n)<c_2g(n)$, but why does this show that $g(n)$ is bounded below by $f(n)$? I would think that it would be ...
3
votes
1answer
222 views

Are there straightforward methods to tell which function has fastest asymptotic growth without a calculator?

For example, suppose I wanted to determine which of the following has the fastest asymptotic growth: $n^2\log(n)+(\log(n))^2$ $n^2+\log(2^n)+1$ $(n+1)^3+(n-1)^3$ $(n+\log(n))^22^{100}$ Are there ...
6
votes
4answers
2k views

Big-O notation Basics, is it related to derivatives?

I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in). On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper ...
0
votes
1answer
153 views

How do you get the upper bound over this recurrence?

$$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n^2}{\log n}$$ I have the solution here (see example 4 in that pdf), but the problem is that they have solved it by guessing. I couldn't make that guess. ...
0
votes
2answers
805 views

proof that a function plus a lower growth function is theta the first function.

my assignment is to (dis)prove the following f(n)+o(f(n))=Θ(f(n)) for example: for all n >= n', n + log(n) = c*n so ...
3
votes
2answers
189 views

asymptotic analysis: what is a basic approach to this?

I am just looking for basic step by step in how to turn a pseudo code algorithm into a function and then how to calculate and show T(n) ∈ O(f(n)), and that T(n)∈ Sigma(f(n)) Also if someone could ...
2
votes
2answers
276 views

A systematic way to estimate the cardinality of a set

Let me take the following set as an example: \[ A = \lbrace \langle a,b \rangle \in \mathbb{N} \times \mathbb{N} : a^2 + b^2 \leq n \rbrace . \] One approach would be to notice that $A$ is the set ...
3
votes
3answers
169 views

A couple of asymptotics exercises

Recently I've been following the chapter on asymptotics in Concrete Mathematics. The subject matter of it is relatively new to me though and I'm having some difficulties dealing with asymptotic ...
4
votes
1answer
3k views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen: Suppose the function $f$ satisfies the recurrence ...
2
votes
4answers
1k views

The asymptotic behaviour of $\sum_{k=1}^{n} k \log k$.

Trying to simplify the following expressions in $n$ to find its order of growth. I want to show the simplification separately from the order of growth $$\sum_{k=1}^{n} k \log k = \Theta(n^2 \log n)$$ ...