Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
3
votes
3answers
1k views

Can someone clarify landau symbols definition please?

I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know ...
3
votes
4answers
78 views

Asymptotic Runtime of Interrelated Functions

I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me... How would I find the asymptotic ...
3
votes
1answer
320 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: ...
3
votes
2answers
1k views

Number of times statement is executed in complex nested loop

I am trying to find out how many times the "statement" is executed by finding its formula based on these loops: ...
3
votes
1answer
2k views

Why is a sequence of n Push, Pop, Multipop operations O(n²)?

From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453: Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The ...
3
votes
2answers
2k views

Is there an NP-complete problem that can be solved in $O(n^{\log n})$ time?

I'm following an online course which has the following (multiple-choice) quiz question: Which of the following statements cannot be true, given the current state of knowledge? Some NP-...
3
votes
2answers
111 views

what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length?

I'm working on an algorithm and I'm trying to figure out its time complexity given the operations it takes to complete a input set of specific length, I have been testing the algorithm with varying ...
3
votes
2answers
532 views

how to prove that nlogn is not Θ(n) without using limits?

i'm studying an algorithms designing and analysis , and i've question about Big-theta how can i prove that nlogn is not Θ(n) without using limits ?
3
votes
1answer
2k views

Is $\Theta$ symmetric?

For example if $$ f(x)= \Theta (g(x)) $$ from the definition of the theta notation, there exist c1 and c2 constants such that $$c_1 g(x) \le f(x) \le c_2 g(x)$$ then if only we took the constants $...
3
votes
2answers
2k views

Methods for Finding Asymptotic Lower Bounds

I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n_0$ for ...
3
votes
2answers
67 views

Is it possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$

I am wondering if it is possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$, i.e. omit the left part. $A$, $B$, and $C$ are all independent from each other. Personally, I think that the ...
3
votes
1answer
1k views

Is O(ln n) “exponentially faster” than O(n)?

I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear ...
3
votes
1answer
3k views

Big O notation of max?

I'm coding a few set comparisons and noting their big O's using different algorithms and set implementations. I got to one particular function and I decided that it is $O(max(n,m))$ runtime. Is that ...
3
votes
1answer
39 views

What does $\omega{(1)}\cdot O(logN)$ mean?

What does $\omega{(1)}$ mean as a factor? In some papers, there exists some asymptotic analysis which comprises a product of multiple Landau notation like $\omega(1)\cdot O(logN)$. In this example, ...
3
votes
2answers
53 views

Does “in-place” for $n$ items imply space dominated by $n$?

Does the characterisation of an algorithm for $n$ items as in-place imply space ∊ $ο(n)$ formally informally ("among coders")?
3
votes
1answer
179 views

Number of Pairs in Array

so hey, I've been recently reading about the Two-Pointer algorithm that allows us to find pairs $(i,j)$ such that $a[i] + a[j] = x$ in $O(m+n)$ instead of the trivial $O(mn)$ time. I was wondering ...
3
votes
2answers
268 views

Expressing that a function converges to 1 with linear rate using Landau notation

I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is ...
3
votes
2answers
113 views

Which of $e^n$ and $2n^2$ grows faster? [duplicate]

How would you prove/disprove that $e^n = O(2n^2)$? It's unclear to me which function grows faster.
3
votes
2answers
94 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form $T(n)=aT(\frac{n}{...
3
votes
2answers
253 views

Time Complexity $\Theta$ vs. $\Omega$ [duplicate]

If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?
3
votes
1answer
2k 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)^...
3
votes
1answer
208 views

Basic Theta-notation question

Let $T$ be a function. Is it true that if $\exists f\forall n,m> 0.\\ \frac m {f(n)} \leq T(n,m)\leq m$ Then $\exists g.T(n,m)=\Theta(m\cdot g(n))$? In words: is such a case, is there a function ...
3
votes
1answer
59 views

The role of asymptotic notation in $e^x=1+𝑥+Θ(𝑥^2)$?

I'm reading CLRS and there is the following: When x→0, the approximation of $e^x$ by $1+x$ is quite good: $$e^x=1+𝑥+Θ(𝑥^2)$$ I suppose I understand what means this equation from math ...
3
votes
2answers
205 views

$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

I'm trying to prove that for arbitrary $c > 0$, $f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$ Intuitively, this seems to be true to me (little-o implies ...
3
votes
1answer
49 views

Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$

Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$. It looks like I need to find a very small growing function $g$ that will satisfy $$\...
3
votes
2answers
739 views

Time complexity of functions that call each other

I'm having trouble reasoning about the time complexity of these mutually recursive functions. This was asked on SO here but the answer there didn't help me. I tried substituting one of the recurrences ...
3
votes
2answers
214 views

Algorithm for finding a mouse hole in a wall in O(n) time

There is this question: As a result of the US Election, a wall is built along the entire Canadian border. You have been told there is a mouse hole in the wall, but it can only be seen when you ...
3
votes
1answer
67 views

Why add a +1 to the constant proving an O(n) bound?

I have calculated a running-time function $T(n) = 4 + 4n$, which is $O(n)$. To determine the constant $C$ given by the relation $|T(n)| < C \cdot g(n)$, we take $\qquad\displaystyle \lim_{n \to ...
3
votes
1answer
67 views

How do I find an upper bound on this recurrence

$f(n)=f(n-\sqrt{n})$ I believe $f(n)\in O(\sqrt{n})$ However I cannot seem to prove it, my intuition comes from the fact that we can remove $\sqrt{n}$ exactly $\sqrt{n}$ times, but if $n$ shrinks ...
3
votes
1answer
924 views

Use of Big-O Notation: Size of Input vs Input

It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size ...
3
votes
1answer
218 views

Proof or refute $n^n = \Omega(n!)$ with the help of Stirling's approximation

I'm trying to proof/refute the following equation: $$n^n = \Omega(n!)$$ Generally I would try to use Convergence Criteria and or l'Hôpital's rule to solve such a problem. $$\lim_{n\to \inf}{{f(n)}\...
3
votes
1answer
89 views

O(f) vs O(f(n))

I first learned about the Big O notation in an intro to Algorithms class. He showed us that function $g \in O(f(n))$ Afterwords in Discrete Math another Professor, without knowing of the first, told ...
3
votes
1answer
460 views

Recurrence relation in 2 variables

When analyzing an algorithm, the following recurrence relation popped up: $T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$ where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$. By applying the Master Theorem inductively,...
3
votes
1answer
427 views

Compare asymptotic WC runtime with measured AC runtime

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations. But this is the worst case,...
3
votes
1answer
141 views

What is the proper runtime for visiting all outgoing edges in an adjacency list?

Suppose that we have a directed graph $G = (V, E)$ represented as an adjacency list. Suppose that we want to list all of the edges incident to some node $v \in V$. We can do this by iterating over ...
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)$ ...
3
votes
2answers
47 views

How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$

In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition \begin{align*} \...
3
votes
1answer
576 views

Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
3
votes
2answers
67 views

Asymptotic growth of $\log(n^n + n)$

I would like to know if my understanding of this is correct: The question asks to show that the Big-Oh of the following function is $O(n\log(n))$ $$ \log(n^n + n) $$ I think the first step is to ...
3
votes
3answers
230 views

How can I solve the recurrence $T(n) = 4T(n/2) + n^2\log^2n$? (without master theorem) [duplicate]

I can not find the appropriate variable to change the second part $n^2\mathrm{log}^2n$.
3
votes
2answers
236 views

Solving recurrences by substitution

I'm going through Cormen et al.'s Introduction to Algorithms and I am a little thrown off by some of the subtleties of solving recurrences with the substitution method. Given the recurrence: $$ T(n) ...
3
votes
1answer
81 views

What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?

For language $L$, we have $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$? It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $...
3
votes
3answers
2k views

Is there any difference between Time Complexity and Running time?

Is time complexity and running time of the program/algorithm one and the same thing? Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that ...
3
votes
1answer
152 views

Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation. Assume that $t(n)= \Theta (1)$ for suffucuently small $n$. $$t(n)=t(\frac{n}{...
3
votes
1answer
95 views

Number of non-XOR gates needed to implement an n-bit boolean function

There are $2^{2^n}$ possible functions that have $n$ boolean inputs and a single boolean output. Some of these functions have very short boolean logic circuits. Some have longer circuits. A classic ...
3
votes
1answer
3k views

Analyzing time complexity for change making algorithm (Brute force)

I'm new to analyzing time complexities and I have a question. To compute the nth fibonacci number, the recurrence tree will look like so: Since the tree can have a maximum height of 'n' and at every ...
3
votes
2answers
79 views

Asymptotics of a recurrence defined with two variables

What is the asymptotic behaviour, in Θ notation, of the smallest function that for any $n_1$ and $n_2$ satisfies the following: $$t(n_1+n_2)≥t(n_1)+t(n_2)+c·\log_2(1+n_2)$$ where $n_1≥n_2≥1$ and $t(1)...
3
votes
1answer
638 views

Complexity of k-way merge with log n arrays of size n / log n

I'm designing an in-place sorting algorithm to sort a collection of size $n$. Near the end of the sorting, it may end up with with $\log{n}$ sorted sub-sequences of size $\frac{n}{\log{n}}$. At this ...
3
votes
1answer
75 views

Asymptotic estimate for $\sum_{k=1}^{N} {\frac{1}{k^2 H_k}}$

I am working on finding the asymptotic estimate for $$ \sum_{k=1}^{N} {\frac{1}{k^2 H_k}}.$$ All I know is that ${\frac{1}{k^2 H_k}}$ is convergent because $${\frac{1}{k^2 H_k}}<\frac{1}{k^2}$$ and ...
3
votes
2answers
427 views

Arithmetic of asymptotic functions

I faced some problem that involves arithmetic over asymptotic functions. These are as follows: Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then [f(n). g(n)] + h(n) is: (a) $Ω(n)$ (b) $O(n)$...

1
3 4
5
6 7
22