Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,004
questions
0
votes
1answer
13 views
Can we apply the Master Theorem to the following recurrence?
Our recurrence is
$$
T(n)=
\begin{cases}
T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\
1 & \text{if $n=1.$}
\end{cases}
$$
I have identified $a = 1 > 0$, and $b = 2 > 1$...
3
votes
2answers
35 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*}
\...
0
votes
1answer
23 views
Bubble sort: how to calculate amount of comparisons and swaps
For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do ...
0
votes
0answers
22 views
proving long asymptotic bounds
I'm trying to find ways this simplify this formula and assuming numbers but that doesn't seem to help, the question is asking to prove or disprove:
$$ 3n(\log_{}n)^2 + 4n = \Omega (2n^2 \log_{}n +1) $...
2
votes
1answer
39 views
Solving a recurrence relation involving square roots
Give an asymptotic upper bound for $$T(n) = \sqrt{n}·T(\sqrt{n})+n+n/\log n. $$
How can I solve this recurrence relation, which involves square roots?
0
votes
1answer
31 views
Find function that satisfy the relation
Can you find the function that satisfy the relation?
$$f(n) = \Theta(g(n)), f(n) = o(g(n))$$
3
votes
1answer
23 views
Prove or disprove that $log^{k}(n) \in O(\sqrt{n}) \forall k > 0$
I'm trying to solve the problem described in the title. By using the free version of wolfram and testing some increasing values of $k$ I get that:
$$\lim_{n \rightarrow \infty} \frac{log^{k}(n)}{\...
0
votes
0answers
12 views
Growth of n/logn vs n^(1+e) [duplicate]
Is $\Theta(\frac{n}{log(n)})$ faster growing function than $\Theta(n^{1+\epsilon})$, where $\epsilon > 0$?
0
votes
1answer
37 views
Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$
I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that?
Algorithm A
...
2
votes
3answers
75 views
How can $\Theta$ and $O$ complexities be different?
From the definition of the $\Theta$-notation,
$$f(n)=\Theta(g(n))\\\implies \exists n_0, \exists c_1,c_2\gt 0, \forall n\gt n_0, c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$$
We can see that the ...
5
votes
2answers
65 views
What constant in the latest fast matrix multiplication is hidden by Big-O notation?
I'm evaluating the theoretical run time of matrix multiplication algorithms as it has improved within the last few decades. Algorithms to solve matrix multiplication run in O(n^w) time, where w has ...
3
votes
0answers
47 views
Does a function that belongs to θ(n) belong to O(n^2)? [closed]
My understanding is that the answer is yes. To be θ(n) implies O(n), which itself implies O(n^2).
In other words, a function that is tightly bounded by n is trivially upper-bounded by n^2 as well.
...
-1
votes
1answer
41 views
confused with Time Complexity [duplicate]
I was reading book related to Time Complexity, and came up with 4 lines of equations that I could not understand properly, could you please explain why are those true?
1) $n = o(n\log\log n)$
2) $...
1
vote
1answer
60 views
Running time of algorithm (effect of j*j in for loops) - Theta Runtime
In Theta notation what are the running times of these algorithms?
Algorithm 1
for i=1..n
j=1
while j*j <= i:
j = j + 1
Since the outer loop ...
2
votes
0answers
37 views
Asymtotic bound for recurrence of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution
What can be an initial guess for finding the tight asymptotic bounds of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution method?
0
votes
2answers
51 views
Runtime complexity of a brute force factoring algorithm? (in terms of bits)
Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
2
votes
1answer
26 views
Proving that $S_1+S_2 \leq f^{-\omega(1)}$
I am trying to show for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c} $ . For a particular $S_1,S_2,f$. Does it suffice to prove there ...
0
votes
0answers
23 views
Time complexity of simple function related to bits
I am wondering about correct answer to this task from a yesterday's test:
A function Pow which calculates $y = a^k$ is given, where $k$ is an
integer of length ...
0
votes
1answer
68 views
How to justify $f(n) = O(g(n))$ [duplicate]
The following question is in my homework:
Is the statement $f(n) = O(g(n))$ true, when $f(n) = n/2 + 4$ and $g(n) = \sqrt{n} + 2\log_2 n + 3$?
I understand how $f(n)$ is the upper bound of $g(n)$. ...
0
votes
0answers
22 views
Asymptotics and logarithms/exponents
We have four categories:
additive constants, multiplicative constants, polynomials, and
exponentials
When determining the growth order of functions, we only care about polynomials and ...
4
votes
1answer
70 views
Exact meaning of $2^{\mathcal{O}(f(n))}$
In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.
For example he says that the running time of a single-tape ...
2
votes
1answer
19 views
Asymptotic Relationship from Limit
F(n) = n-100
G(n) = n-200
I am trying to show the asymptotic relationship between these two functions using limits.
I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c.
...
-2
votes
1answer
26 views
Help with Big-O homework [duplicate]
"er" is the Danish equivalent of "is" in English. I need some help with the square root one. Additionally, it would be nice to know if the other ones are correct.
4
votes
2answers
166 views
Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?
The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following:
$$ \sum_{i=1}^n O(i) $$
is not the same as (I'm not using DNE because the book explicitly ...
0
votes
1answer
31 views
Why does Union-Find have time complexity O(N + M lg* N) with the “log star N”?
The time complexity of Weighted Union-Find with Path Compression, for M union-find ops and N objects is said to be
$$ O(N + M \lg^*N) $$
and the $ lg^*N $ is "log star N" and is iterated logarithm. ...
0
votes
1answer
18 views
When the data size and processor speed are both multiplied by 10, then a linearithmic algorithm takes double the time to finish?
Robert Sedgewick mentioned, if a computer can handle 10x data and the processor is also 10x as fast, then a $ O(n^2) $ algorithm actually runs slower than before.
Is this the correct idea when a ...
2
votes
1answer
67 views
O(1) distinct elements in an array implies?
Could someone explain the following question -
Given the following statement viz. Consider an input array a[1..n] of arbitrary numbers. It is given that
the array has only O(1) distinct elements. ...
3
votes
1answer
203 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 ...
4
votes
1answer
579 views
What does $|V|=O(|E|)$ mean?
I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
1
vote
1answer
52 views
Analyzing time complexity of solution in tutorial
Could someone explain time complexity of solution of in this tutorial?
I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$.
What I figured so far is, for ...
1
vote
0answers
21 views
Useful conditions for proving super polynomial lower bound for some kind of recurrences
Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$
Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
3
votes
2answers
56 views
Struggling to understand the symbolism around the big oh formal definition
I'm struggling to understand what exactly T(n), and f(n) is in the above text:
When we compute the time complexity T(n) of an ...
0
votes
0answers
11 views
Mapping every character to its next occurrence based on the number of unique characters between the occurrences
To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
0
votes
1answer
63 views
Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?
I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access...
My question though ...
2
votes
1answer
58 views
runtime of 2 dependent nested for loops [duplicate]
for (i=1; i<=n ;i=i*2){
for (j=1; j<=i ;j++){
basic_step;
}
}
Regarding the above nested loops, I can't seem to understand why is the following ...
0
votes
3answers
64 views
Is there a unit of measurement that can express code execution speed in absolute terms?
I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
1
vote
1answer
22 views
Time complexity of rotation array m times using temporary array
I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the ...
1
vote
1answer
61 views
How to find an algorithm's complexity from actual running times
I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of ...
1
vote
0answers
136 views
Approaches for analyzing the work, critical path length and parallelism
I'd like to know where to find references and approaches on how to analyze the work, critical path length and parallelism of algorithms.
In particular, for solving the type of homework problems below:...
1
vote
1answer
20 views
Proof involving asymptotic complexity
The question in Proof of big-o propositions asked to prove:
$O(f(n))=O(g(n))\iff\Omega(f(n))=\Omega(g(n))\iff\Theta(f(n))=\Theta(g(n))$
The accepted answer starts the proof with:
Suppose that $...
1
vote
1answer
42 views
Recursion Time Complexity (Half n' Half)
This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity:
Input: string $s = s_1,\ldots,s_n$, integer $k$
Go over all symbols $s_1,\ldots,s_n$, one by one
...
1
vote
1answer
52 views
Akra-Bazzi method integral diverges
I want to solve this recursion:
$$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$
My attempt and issue:
None of the cases for master theorem apply here.
I tried using Akra-Bazzi method (https://en....
1
vote
0answers
24 views
Cuckoo hashing with a stash: how tight are the bounds on the failure probability?
I was reading this very good summary of Cuckoo hashing.
It includes a result (page 5) that:
A stash of constant sizes reduces the probability of any failure to
fall from $\Theta(1/n)$ to $\Theta(...
1
vote
1answer
29 views
Asymptotic notation and random variables
I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values).
Suppose that the two ...
0
votes
0answers
31 views
Deducing $3^f = o(3^g)$ from $f = o(g)$
I really need help solving the following question:
Given:
$$f(n) = o(g(n))$$
Prove:
$$3^{f(n)} = o(3^{g(n)})$$
My attempt:
I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0 $.
I need to ...
1
vote
2answers
77 views
Average case analysis of linear search
Based on CLRS question 2.2:
Consider linear search again. How many elements of the input
sequence need to be checked on the average, assuming that the element being
searched for is equally likely to ...
3
votes
1answer
55 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 ...
1
vote
2answers
128 views
Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?
This is a question posted for extra practice (i.e., not for credit):
Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain.
I'm not sure ...
2
votes
2answers
39 views
How to use Master Theorem with strange format of $b$ parameter?
I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as:
$$T(n)=\begin{cases}
6 &\text{ if } n=0,\\
T(n-1) + 6n + 6 &\text{otherwise.}
\end{cases}$$
How can I apply the Master Theorem to ...
2
votes
2answers
87 views
Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)
We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently:
$$T(n)=\begin{cases}
0 &\text{ if } n=0,\\
3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.}
\end{cases}$$
Prove that for ...
