2
votes
2answers
81 views

Is there a closed form for $\sum_{j=1}^{n} j^2\log{j}$?

Question Is there a closed form for $\sum_{j=1}^{n} j^2\log{j} = 1\times0 + 2^2\times\log{2} + 3^2\log{3} + \dots + n^2\log{n}$? I'm trying to look for the simplest $\Theta$ notation. Attempt Let ...
2
votes
1answer
28 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
3
votes
0answers
51 views

Increasing Growth Rate Challenge [closed]

why from left to right, we have increasing in growth rate? any description for some usual equivalence formula for each of them?
1
vote
1answer
37 views

Closed form for estimated sum with different asymptotic bounds?

I found asymptotic lower and upper bounds for a summation as follows: $$ 1 - O\left(\frac{\log_2^2 n}{n}\right) \le \sum_n f(n) \le 1 + O\left(\frac{1}{n}\right).$$ If you want to write it in a ...
0
votes
1answer
19 views

How do you solve a recurrence with a functin through induction?

I found the answer in part-A by substitution, as O(n) from; T(n/2^k) = T(1).... n/2^k = 1..... so k = 1og2(n)..... T(log2(n)) = T(n/n)+5.... so O(n) IS THE ANSWER, Correct me if am wrong because am ...
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
62 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
28 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
34 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
31 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 ...
-1
votes
0answers
22 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
35 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?
-1
votes
2answers
62 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
49 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
31 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
43 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
53 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
41 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
49 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
61 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
172 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
82 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
213 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
610 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
79 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
83 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
238 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
59 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
602 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
57 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
94 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
159 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
338 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
310 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
122 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
102 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
145 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
159 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
4k 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 ...