Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
4
votes
3answers
640 views

Why is $n \log \log n$ not tightly bounded by $n$?

I don't understand why $n \log \log n $ is not $\Theta (n)$. Suppose we give $n$ a value of $10,000$. Then $n \log \log n$ is $6020.6$. So isn't $n \log \log n$ upper- and lower-bounded by $n$, as $n ...
0
votes
1answer
163 views

Explanation of a specific recurrence with respect to Master Theorem

Concerning the Master Theorem. I have found the following equation as the base of analysis: $\quad T(n) = aT(n/b) + \Theta(n^k)$ but I also found the following: $\quad T(n) = aT(n/b) + \Theta(...
4
votes
4answers
7k views

Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?

I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up). Why does ...
2
votes
2answers
1k views

Running time of a nested loop with $\sum i \log i$ term

So I have the following pseudo-code: Function(n): for (i = 4 to n^2): for (j = 5 to floor(3ilog(i))): // Some math that executes in constant time So ...
19
votes
1answer
651 views

Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
23
votes
5answers
10k views

Is O(mn) considered “linear” or “quadratic” growth?

If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (...
3
votes
2answers
2k views

How to the examples for using the master theorem in Cormen work?

I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples $3T( \frac{n}{4} ) + n\log(n)$ $2T( \frac{n}{2} ) + n\log(n)$ ...
6
votes
1answer
719 views

Master theorem and constants independent of $n$

I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version): $$T(n)=4T(n/2)+O(r)$$ $r$ is independent of $n$. Case 1 of the Master theorem applies ...
3
votes
1answer
1k views

Solve a recurrence using the master theorem

This is the recursive formula for which I'm trying to find an asymptotic closed form by the master theorem: $$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$ I started with $a=9,b=27$ and $f(n)=(n\cdot \lg n)^...
6
votes
1answer
173 views

Finding lambda of Master Theorem

Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$. That should be case 1 of the Master theorem because $n^{1/2}>\log(n)$. There is also a lambda in case 1: ...
10
votes
3answers
674 views

Sums of Landau terms revisited

I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success. Now, over here our recurrence guru JeffE ...
2
votes
1answer
242 views

asymptotic notations with two exponents

I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these ...
1
vote
1answer
2k views

Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?

From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity. Can it ...
3
votes
1answer
104 views

Showing bounds of a recurrence

I'm working exercises on solving recurrences, just using subsitution, master theorem is after this chapter. I'm sort of stuck on one of the exercises. It states that: The solution of $T(n) = 2T(\...
1
vote
1answer
80 views

How is this algorithm in these two complexities?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
2
votes
1answer
163 views

Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?

The following is an excerpt from CLRS: The definition of $g(n)$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever n is ...
3
votes
2answers
494 views

If $f(n) = \Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$?

The following is an excerpt from CLRS: $\Theta(g(n))= \{ f(n) \mid \text{ $\exists c_1,c_2,n_0>0$ such that $0 \le c_1 g(n) \le f(n) \le c_2g(n)$ for all $n \ge n_0$}\}$. Assuming $n \in \...
2
votes
1answer
262 views

Input to make worst case on big O not possible?

Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a ...
8
votes
3answers
1k views

Why is $3^n = 2^{O(n)}$ true?

$3^n = 2^{O(n)}$ is apparently true. I thought that it was false though because $3^n$ grows faster than any exponential function with a base of 2. How is $3^n = 2^{O(n)}$ true?
4
votes
1answer
118 views

Height of AVL after entries

Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$ elements. After the insertion of $n^2$ elements, what would be its height? My idea: the height of an AVL tree is ...
0
votes
3answers
145 views

How to guess the value of $j$ at the end of the loop?

for ( i = n , j = 0 ; i > 0 ; i = i / 2 , j = j + i ) ; All variables are integers.(i.e. if decimal values occur, consider their floor value) Let $\text{val}(...
2
votes
3answers
408 views

When does $1.00001^n$ exceed $n^{100001}$?

I have been told than $n^{1000001} = O(1.000001^n)$. If that's the case, there must be some value $n$ at which $1.000001^n$ exceeds $n^{1000001}$. However, when I consult Wolfram Alpha, I get a ...
7
votes
2answers
153 views

Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$

The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem For instance, the Arora-Barak book ...
1
vote
1answer
3k views

Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$ [duplicate]

Possible Duplicate: Solving or approximating recurrence relations for sequences of numbers I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is $ T(n) = O(n \log(n))$ But how do you get to ...
2
votes
1answer
722 views

Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$

$T(n)=2T(n/2) + n\log^2(n)$. If I try to substitute $m = \log(n)$ I end up with $T(2^m)=2 T(2^{m-1}) + 2^m\log^{2}(2^m)$. Which isn't helpful to me. Any clues? PS. hope this isn't too localized. ...
3
votes
1answer
313 views

Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$?

I'm currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples. The question equation: ...
0
votes
1answer
93 views

Finding $c$ and $n_0$ for a big-O bound

A book I am reading demonstrates how $5n^3 + 2n^2 + 22n + 6 = O(n^3)$, which I believe is true. After all, there exists a value $c$ for which $cn^3$ is always greater than $5n^3 + 2n^2 + 22n + 6$ for ...
2
votes
2answers
159 views

Prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$

Hopefully this is the right section. I need to prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$. From the basic principle of Big-O notation, I know I need to find two numbers $c$ and $N$ so that $f(n) \le ...
4
votes
2answers
3k views

Confusion about big-O notation comparison of two functions

On page 16 of this algorithms book, it states: For example, suppose we are choosing between two algorithms for a particular computational task. One takes $f_1(n) = n^2$ steps, while the other takes ...
32
votes
2answers
1k views

How asymptotically bad is naive shuffling?

It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly: ...
1
vote
1answer
2k views

Big Omega of $n \log n$

While studying master method at recurrences topic I'm stacked at a point. It is written in the book as: $T(n) = 3T(n/4) + n \log n$, we have $a = 3, b = 4$, $f(n) = n \log n$, and $...
2
votes
2answers
167 views
1
vote
1answer
1k views

How to prove transitivity in small-o of asymptotic analysis?

Here is my proof, but I am not sure whether it is correct. We know: $\qquad \begin{array}{l} \forall {c_1},\exists {n_1},0 \le f\left( n \right) \le {c_1}g\left( n \right),\forall n \ge {n_1} \\ \...
2
votes
1answer
107 views

Recursive complexity with change of variable

I face a problem with computing a complexity. I have this equality : $P(u) = (\sqrt{u}+1)P(\sqrt{u}) + \theta(\sqrt{u})$ And I want to prove that $P(u) = O(u)$ This is how I process : I put $m = \...
15
votes
2answers
14k views

Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
7
votes
2answers
881 views

Definition of $\Theta$ for negative functions

I'm working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $\Theta$ notation. I understood the beginning definition of:...
0
votes
2answers
97 views

Why bound of linear function is same as that of quadratic equation

I am learning algorithms. So, I came along with something very interesting. The asymptotic bound of linear function $an+b$ is $O(n^2)$ for all $a>0$. This is same as for $an^2 + bn + c$. But ...
5
votes
1answer
2k views

Subtracting lower-order term to prove subtitution method works

Substation method fails to prove that $T(n)=\Theta(n^2) $ for the recursion $T(n)=4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2$. I don't understand how to subtract off lower-...
6
votes
1answer
273 views

what is the complexity of recurrence relation?

what is the complexity of below relation $ T(n) = 2*T(\sqrt n) + \log n$ and $T(2) = 1$ Is it $\Theta (\log n * \log \log n)$ ?
2
votes
1answer
2k views

Finding the number of leaves in a imbalanced recursion tree

I'm going through the MIT Online Course Videos on Intro. to Algorithms at here at around 38:00. So we have a recursion formula $\qquad T(n) = T(n/10) + T(9n/10) + O(n)$ If we build a recursion tree ...
12
votes
6answers
20k views

n*log n and n/log n against polynomial running time

I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\...
5
votes
3answers
296 views

Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
1
vote
3answers
675 views

Value of constants in Big Theta notation

In Big Theta notation used for defining the running time of an algorithm, are the constants $c_1$ and $c_2$ different for every value of $n$? Definition: $\qquad \displaystyle \Theta (g(n)) = \{ f(n)...
11
votes
2answers
262 views

Is $O$ contained in $\Theta$?

So I have this question to prove a statement: $O(n)\subset\Theta(n)$... I don't need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $\Theta(n)\...
5
votes
3answers
428 views

Asymptotic growth rate of $f(n)$ and $f(n+1)$

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous positive function, where $f(n)$ is integer for each integer $n$. Prove or disprove whether the following always holds: $\qquad f(n+1) = \...
44
votes
2answers
3k views

What is the meaning of $O(m+n)$?

This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
7
votes
1answer
863 views

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$. The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing $\qquad \...
13
votes
2answers
640 views

Do non-computable functions grow asymptotically larger?

I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all ...
1
vote
1answer
384 views

Recursion for runtime of divide and conquer algorithms

A divide and conquer algorithm's work at a specific level can be simplified into the equation: $\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$ where $n$ is the size of ...
7
votes
2answers
455 views

$\log^*(n)$ runtime analysis

So I know that $\log^*$ means iterated logarithm, so $\log^*(3)$ = $(\log\log\log\log...)$ until $n \leq 1$. I'm trying to solve the following: is $\log^*(2^{2^n})$ little $o$, little $\omega$, ...