1
vote
1answer
31 views

Computational complexity and the big $\mathcal{O}$

I have a question about this Big $\mathcal{O}$ problem. I have the question down $90\%$, but the other $10\%$ isn't getting to me. I will write out the entire question and I'll point out the step, ...
2
votes
1answer
55 views

Prove that limits can be used for asymptotic analysis

True or false: If f(n)=$\Theta$(g(n)), then $$\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}$$ exists and is equal to some real number. I'm not sure what needs to be done to demonstrate this. I do ...
0
votes
1answer
26 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
0
votes
1answer
31 views

Master Theorem , Polynomial, recurrences

Going through Master's theorem for recurrences but I am seriously confused as what it means when we say that function f(n) is polynomially greater than function g(n) (Case 3) and how can one check ...
0
votes
1answer
28 views

Is $f(n) + O(f(n)) = \theta(f(n))$?

I've been asked to show whether this is always, never or sometimes true. I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation ...
0
votes
0answers
21 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
0
votes
1answer
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?
0
votes
2answers
61 views

Is $x^2+25x+4 \in \mathcal{O}(x^2)$? If yes how? If no why not? [closed]

Is $x^2+25x+4 \in \mathcal{O}(x^2)$ ? if yes how ?, if no why? i know x^2+25x+4≤25x^2+25x+25≤25x^2+25x^2+25x^2=75x2 for some x what confuses me is x^2+25x+4≤25x^3+25x+25≤25x^3+25x^3+25x^3=75x3 ...
0
votes
1answer
36 views

Using arithmetic progression sum to show an algorithm is both $\Theta(n^2)$ and $O(n^2)$

Exercise 4 in http://discrete.gr/complexity/ askes to give an arithmetic progression sum to show that the following algorithm is both $O(n^2)$ and $\Theta(n^2)$. ...
0
votes
1answer
30 views

Asymptotic behaviour of a couple of special functions (features exponentials and logarithms)

I'm dealing with a couple of functions: $n \log n$, $( \log \log n)^{ \log n}$, $( \log n)^{ \log \log n}$, $n e^{\sqrt{n}}$, $( \log n)^{ \log n}$, $n 2^{ \log \log n}$, $n^{1+1/( \log \log ...
1
vote
1answer
40 views

Question about Big O Notation

I don't seem to understand big-O notation very well. If someone would explain it to me as well as explain how this problem would work Let f(n) = (3$^n$$^+$$^1$ - 3)/2. For each of the following ...
1
vote
2answers
41 views

Trouble understanding Big O notation for a sum of n integers [duplicate]

This problem is an example in a Discrete Math textbook. How can big-O notation be used to estimate the sum of the first n positive integers? Solution: Because each of the integers in the sum of the ...
2
votes
0answers
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 ...
0
votes
3answers
38 views

Big O question related to nested loop

So i have code that is a nested loop and the outside loop executes n times but the inside loop executes $n\sqrt{n}$ times. So would my worst case scenario still be $O(n^2)$?
0
votes
1answer
41 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
56 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 ...
0
votes
2answers
150 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
81 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
54 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 ...
3
votes
2answers
181 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
604 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
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)$
4
votes
1answer
90 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
80 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
37 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
54 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
107 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
58 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
211 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
58 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} \ ...
1
vote
2answers
535 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
52 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
92 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
158 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
318 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
299 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
121 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
101 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
107 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
144 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
157 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
3k 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 ...
32
votes
0answers
737 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
254 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. ...