Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
981
questions
0
votes
1answer
17 views
Asymptotic Analysis
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
190 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 ...
-1
votes
0answers
13 views
What recursive T(N) function typically can conclude the algorithm is O(n ^ 2), O(n log n), O(n), and O(log n)?
Is it true that some common forms of recursive T(n) can give the following conclusions?
When
T(n) = T(n/c) + b where c is a constant > 1, b is any constant
...
-1
votes
0answers
28 views
Is optimizing from O(n log n) to O(n) considered to be premature optimization? [closed]
For example, the 2-sum problem: given an array of N distinct numbers, find all possible pairs of numbers that add up to K.
Sedgewick's Algorithm book seems to stop at O(n log n), while the "best" ...
4
votes
1answer
569 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
45 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
20 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
53 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
54 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
48 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
61 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
21 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
60 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
16 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
37 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
21 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
22 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
28 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
39 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
114 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
38 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
86 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 ...
1
vote
1answer
55 views
Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor
I was trying to solve the following question while reviewing master theorem.
Which of the following asymptotically grows faster.
(a) $ T(n) = 4T(n/2) + 10n $
(b) $ T(n) = 8T(n/3) + 24n^2 $
(c) $ T(...
0
votes
1answer
45 views
3
votes
2answers
171 views
Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?
I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
0
votes
1answer
31 views
Trouble finding what this recurrence solves to [duplicate]
I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$
I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.
3
votes
2answers
127 views
1
vote
2answers
34 views
What does “bounded above” mean in Family of Bachmann–Landau notations?
Per wiki
|f| is bounded above by g (up to constant factor) asymptotically
with this concrete example,
$$f(n) = \log n$$
$$g(n) = n^c = n^{0.000001}$$
Does "bounded above (up to constant factor)...
0
votes
0answers
30 views
how to compute $O(n^{0.000001})$ [duplicate]
this MIT course gives a formula about Big O
$$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$
going through wiki, i cannot find a similar Big O properties or usages.
how to compute $O(n^{...
1
vote
0answers
48 views
which rule can conduct this formula $\log n = O(n^{0.000001})$? [duplicate]
i am learning this post about Big O, which gives this formula
$$\log n = O(n^{0.000001})$$
why is that?
2
votes
2answers
1k views
Are “of the order of n” and “Big O” the same thing?
I am learning from the MIT course Introduction to Algorithms.
The professor says:
Now, remember $\Theta(n)$ is essentially something
that says "of the order of $n$".
What does "of the order ...
0
votes
0answers
14 views
How can I assign the following functions f2,f3,f4 to the best possible (mostly restricted) asymptotic class? [duplicate]
Try a couple of ways but still having a problem to find the specific asymptotic class for each function.
¿Any reference to find the solution o aproach?
1
vote
1answer
35 views
Asymptotics of a sinusoid
Consider the function
$$
f(n) = 2n^2 |\sin(\pi \cdot n/2)|.
$$
Which of the following classes does $f(n)$ belong to?
$$ O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2). $$
I'm working in this ...
2
votes
2answers
177 views
Formulating the master theorem with Little-O- and Little-Omega notation
In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this:
Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
0
votes
0answers
25 views
Calculating the Complexity of a Two Part Algorithm
This is in relation to this post I made. I eventually solved this by the following approach:
Take the un-ordered file with all the purchasing data and use the UNIX ...
2
votes
1answer
28 views
Asymptotic analysis with factorial and exponential
I'm solving a complexity question where I have:
$$ n!/2^n $$
The goal is to find an upper bound for this.
My idea is using the fact that:
$$ n! = O(n^n)$$
$$ n!/2^n = O((n/2)^n) = O(n^n)$$
But is ...
2
votes
2answers
402 views
All superlinear runtime algorithms are asymptotically equivalent to convex function?
Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?
All the examples that I could think of satisfy the above ...
0
votes
0answers
33 views
Minimization with asymptotic assumption
Given the function
$g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with}
\left\{\begin{matrix}
a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\
b\leq a! \\
c\leq (n-a)! \\
\end{matrix}\right.
\Big\}...
2
votes
1answer
22 views
Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$
Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at ...
0
votes
0answers
36 views
How can I prove the linear time search algorithm takes O(n) time? [duplicate]
The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation ...
1
vote
1answer
26 views
Comparing different asymptotic notations
Suppose we have 3 algorithms complexity times at the worst case:
A = $O(nlogn)$
B = $O(n\sqrt{n})$
C = $\Theta(n)$
In my opinion, it is not possible to define the best solution, since we don't know ...
7
votes
1answer
416 views
Asymptotics question
Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?
I am really stuck and I tend to believe it's true, but I don't know how to prove it.
Any help would be appreciated!
2
votes
3answers
63 views
What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + … + (n-1)2 + n$?
My best guess is that the series
$$ \sum_{i=1}^n i(n-(i-1)) $$
becomes
$$ 2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg] $$
So the highest term is $n^2$ and ...
1
vote
2answers
131 views
Traveling Salesman Problem: Big O Complexity of Algorithm
I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused.
The Traveling Salesman problem (TSP) is famous. Given a list of
cities and the distances ...
0
votes
1answer
25 views
Is this computational complexity of the k-NN (custom distance) correct?
I read on a book that in general k-NN (no optimizations), given
$d$ dimensions
$n$ examples
every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
0
votes
0answers
21 views
Asymptotic Question [duplicate]
Hi how do I find the asymptotic bound for the recurrence T(n) = T(n/2) + T(n/4) + T(n/8) + n?
Can I use master theorem or Substitution method only?
If so, I need some help for substitution method. My ...
