1
vote
1answer
34 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
1
vote
1answer
41 views

Prove or disprove: $ \frac{3x^3+2x+1}{x+2} $ is $ \theta (x^2) $.

Prove or disprove: $ \frac{3x^3+2x+1}{x+2} $ is $ \theta (x^2) $. I know that $f(x)$ is $\theta (g(x)) $ if it is both $ O(g(x)) $ and $\Omega (g(x))$ when $ x > n$ I reasoned that $f(x)$ is ...
2
votes
2answers
28 views

Big-O Function for f(x)

I'm currently taking a Discrete Mathematics course which just started the chapter on The Growth of Functions. A (very) brief overview was given in lecture that covered the Big-O definition. Let ...
2
votes
1answer
60 views

Asymptotic Function proof?

I am doing questions from past exams and I stumbled upon this one. I have no idea how to go about solving it.I never had any logarithmic functions in my previous bigOh proofs nor have I had to use ...
2
votes
0answers
28 views

Prove the big theta

I need to find a $n_0$ and $k$ for Big Oh and an $n_0$ and $k$ for Big Omega, to find a big theta bound for: $5n^2 - 9n = \theta(n^2)$ Can anyone help me and show me how to find these for this ...
0
votes
1answer
52 views

Big Theta Proof Tightness

I found that $n_0 = 1 $ and $k=5$ for Big Oh, but I am somewhat confused on how to prove big omega as I have a negative sign in my expression. Furthermore by showing big oh and big omega, am I showing ...
0
votes
1answer
32 views

Proving $\lg n!=\Omega(n\lg n)$

In the answer given in the book for the proof of $\lg n=\Omega(n\lg n)$ there are several steps which I don't understand . $$\lg n!=\lg n+\lg(n-1)+\lg(n-2)+ ....+\lg(2)+\lg 1$$ Then it says that ...
5
votes
1answer
27 views

Question about Growth Rates

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
2
votes
2answers
85 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
32 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.
4
votes
0answers
54 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
44 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
33 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
66 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
30 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
37 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
46 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
1answer
40 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
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 ...
0
votes
1answer
63 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
44 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
93 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
40 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
47 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
53 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
71 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
205 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
83 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
283 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
613 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 ...
0
votes
1answer
117 views

Big $O$ and Big $\Theta$ proof

Use definitions to prove: If f and g are nonnegative, and f(n)=$\Theta$(h(n)) and g(n)=$O$(h(n)), then f(n)+g(n)=$\Theta$(h(n)) I know that f(n)=$\Theta$(h(n)) means that c|h(n)| <= |f(n) | ...
-2
votes
2answers
92 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
91 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
92 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
39 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
1answer
71 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
127 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
278 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
62 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
55 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
692 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
65 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
98 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
161 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 ...