Tagged Questions

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 ...
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.
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?
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 ...
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 ...
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, ...
63 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 ...
28 views

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) = ... 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 ... 1answer 34 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 ... 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 ... 1answer 36 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? 2answers 63 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 ... 1answer 51 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)$. ... 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 ...
43 views

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 ...
55 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 ...
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 ...
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)$?
51 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?
63 views

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 ...
80 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)$
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 ...
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))$.
85 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 ...
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?
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 ...
107 views

609 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 ...
58 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 ...
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}$ ...
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 ...
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. ...
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 ...