Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,431
questions
2
votes
1
answer
20
views
Expected number of mistakes grows logarithmically in number of iterations - improving performance?
I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we ...
- 21
2
votes
1
answer
384
views
Asymptotics of the sum of a geometric series
I have a parameter $q$ which is the probability of selecting a vertex (among $n$ vertices...) to be in a certain set.
I am constructing the sets in an iterative way, having the vertex $v_i$ be in the ...
- 125
1
vote
1
answer
66
views
Sorting rational numbers in linear time
I am currently studying algorithms and computational complexity at University.
I have recently got through three questions I found in an old exam:
Is it possible to sort in asymptotically linear time ...
- 11
1
vote
1
answer
56
views
Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth
As stated in the question title, if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then how can we show $g(n)$ also has polynomial growth?
$g(n)=\Theta(f(n))$ gives us $0\leq c_1f(n)\leq g(n)\...
- 151
0
votes
1
answer
34
views
How are pointers modeled on bit-based computer models?
Why bit-based computer models?
The perhaps most commonly used computer model is a random access machine that can store natural (or even real) numbers in infinitely many cells indexed by natural ...
- 103
0
votes
1
answer
34
views
find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$
We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and
assume $T(1)$ is a constant. Find asymptotically tight bounds
$\Theta(f(n))$ for $T(n)$.
There's something that confuses me. We ...
- 151
0
votes
1
answer
55
views
Find time complexity of $T(n)=3T(n-2)+O(n)$
I try to find the time complexity of following recurrence relation:
$$T(n) = 3T(n-2) + O(n)$$
After subtitution,I get:
$$T(n)=3^{\frac{n}{2}}T(0)+\sum_{i=0}^{\frac{n}{2}-1}3^iO(n-2i)$$
I wonder if the ...
- 3
1
vote
0
answers
23
views
Upper bound via standard manipulation in proof of semi-private learning
I have been reading a paper on private learning [1].
In the proof of lemma 3.3. they claim that
$$
2\left(\frac{2e n_\text{pub}}{d}\right)^{2d}e^{-\alpha n_\text{pub}/4}
$$
is upper bounded by $\beta$ ...
0
votes
1
answer
46
views
Why, for $f(n) = n \cdot \sqrt n$ and $g(n)=n(\log n)^5$, we have $f = \omega(g)$? log is base 2
Could you please explain me why that's the case?
user163425
0
votes
0
answers
19
views
Time complexity summations
How to calculate the time complexity of a algorithm which contains while loops or if statements using summations? I only know how they work with the for loops. And I'm guessing the if loop are ...
- 1
0
votes
1
answer
34
views
Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?
Which function grows faster:
$$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$
Which is true?
$f(n) = O(g(n))$
$g(n) = O(f(n))$
i.e., $f(n) = \Theta(g(n))$
none of the above?
For lower values of ...
- 1
0
votes
1
answer
35
views
Proving asymptotic classes
I am trying to teach myself asymptotic notations. I feel like I'm in over my head. I read the explanations in the text book, and Khan Academy. But when I try to do proofs, I can't grasp anything.
I'm ...
- 1
0
votes
1
answer
65
views
Asymptotic equivalence allows difference by a constant factor?
Wikipedia and other sources define "asymptotically equivalent" as: two functions $f$ and $g$ are asymptotically equivalent if:
$$
\lim\limits_{x \to\infty}\frac{f(x)}{g(x)}=1
$$
But we ...
0
votes
2
answers
48
views
From these functions, how to determine which grows faster without graphing?
How are you intuitively able to tell the Big-Oh of the functions and what order they are on?
$$f(n)=3^n$$
$$g(n)=5^{3log_3{n}}$$
Note this is $5$ raised to $3log_3n$
$$h(n)=1024^{log_2n}$$
1
vote
3
answers
97
views
Is $n^{1.03} = \Omega(n \log \log n)$?
We had this problem on our Algorithms final. It threw me off because if $\log$ is $\log_2$ then graphing the function shows this is not true, but if $\log$ is $\log_{10}$ then it looks like it is. How ...
- 117
-1
votes
3
answers
55
views
Can anyone help explain why the time complexity for this is O(n)
So ive already tried lookig at it but i just get O(nlogn) which is not correct
there were some clues like using a geometric series where 1/2+2/4+3/8+i/2^i<2 but idk how to implement that what ...
- 1
0
votes
2
answers
65
views
Subtracting Two same asymptotic values
I am dealing with two values $a$ and $b$ such that they grow at the same asymptotic rate, i.e., $O(\frac{1}{\sqrt{N}})$. I want to achieve a reasonable bound for the difference $a - b$. When I go into ...
-1
votes
2
answers
71
views
Finding asymptotically tight upper bound of a recursion relation
Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$
I tried to solve it by applying iteration:
$$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{...
- 99
2
votes
6
answers
1k
views
Assuming constant operation cost, are we guaranteed that computational complexity calculated from high level code is "correct"?
Edit: Since this post is gaining traction, I feel the need to clarify that the purpose of this is to see if asymptotic and constant factor estimations calculated from high level code implementations ...
- 549
-1
votes
1
answer
45
views
Solve Recurrence Equation: 𝑇(𝑛)=𝑇(𝑛−4)+𝑛^2
I'm trying to practice recurrence equations, so I'm trying to solve this typology by unfolding method.
I was wondering if what I write below was correct and obviously the result:
$T(n) = n^2 + T(n-4) =...
- 121
0
votes
0
answers
6
views
Asymptotics Accounting for Invocation Frequency in the Context of the broader system
I did some thinking and analysis this evening and I'm wondering if what I'm pointing out here is interesting:
https://medium.com/@nwcodex/invocation-asymptotics-runtime-cost-based-on-the-anticipated-...
0
votes
2
answers
168
views
When does Quicksort go from O(n log n) to O(n^2)?
Quicksort is O(n log n) average case, and O(n^2) worst case. The worst case occurs if one side of the pivot contains all of the elements and the other side contains none. However, I think the worst ...
0
votes
0
answers
34
views
0
votes
0
answers
23
views
Shell algorithm knuth sequence time complexity analysis
Given this shell sort algorithm implementation:
...
- 1
1
vote
0
answers
17
views
Complexity of m bit multiplication & division [duplicate]
In PRIMES IS IN P paper, page 6 under Time Complexity section, authors have mentioned "In these calculations we use the fact that addition, multiplication, and division operations between two m ...
- 155
1
vote
2
answers
92
views
Given an array of size $n$, return a sorted array of floor($n^k$) elements for some $k<1$
We are given an array of size $n$ (it is not specified if we have an integer array, a specific range or any other assumptions), which might be unsorted, and a real number as a
constant $k<1$. We ...
0
votes
1
answer
63
views
Comparisons using Quicksort with the median as the pivot
Background
Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm:
Quicksort($a$):
(1) If length($a$) $...
- 103
0
votes
0
answers
16
views
Need help verifying the complexity of an algorithm [duplicate]
I have the following algorithm which takes as an input a non negative integer n :
i = n
while i > 0 do :
$\,$ $\,$ $\,$ $\,$i = i - 1
$\,$ $\,$ $\,$ $\,$j = 1
$\,$ $\,$ $\,$ $\,$ $\,$ $\,$ $\,...
0
votes
0
answers
38
views
Researching the complexity of a dynamic array with insert-last(x) and delete-last() operations
In this question I need your help researching time complexity of a dynamic array with insert-last(x) and delete-last() operations:
We define a data structure and call it dynamic array, we define the ...
- 1
0
votes
1
answer
33
views
if f(n),g(n) =! 0 , for every n > 0 , and f(n) = Ω(g(n)) , then does this mean that 1/f(n) = O(1/g(n))
Basically what i am trying to prove is this :
$f(n),g(n) \neq 0\quad , n>0 \ \ \ \ and f(n)=Ω(g(n)) \ \ \ , \ then \frac{1}{f(n)}=O(\frac{1}{g(n)}) $
I guess that if we take the definition of $f(...
1
vote
1
answer
56
views
The value of $r$, with $r≤ b$, that minimizes the expression $(b/r)(n+2^r)$ in the analysis of the radix-sort algorithm
In chapter 8 of the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, lemma 8.4 is proved. (my question is after the proof of the lemma)
Given $n$ $b$-bit numbers ...
- 121
3
votes
2
answers
148
views
An algorithm that is $O(n^{\log(n)})$
After having searched for a while, and after having read this
https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities
I was just wondering: is ...
- 131
1
vote
2
answers
46
views
If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?
It is quite easy to prove that f(n) + g(n) ∈ Ω(h(n)), but I am having trouble with proving/disproving that f(n) + g(n) ∈ O(h(n)).
Someone suggested that this question answers mine, which it doesn't. ...
- 23
0
votes
5
answers
224
views
Is $n^n$ is a big-oh n factorial
Is it true or false that $n^{n} \in \mathcal{O}(n!)$ ?
Any suggestions how to prove/disprove this statement?
- 3
0
votes
5
answers
152
views
Find the asymptotic bound for the recurrence relation: $T(n) = T(\sqrt{n}) + 5n$
I've tried to expand the recursion:
$$T(n) = T(n^{\frac{1}{2}}) + 5n = T(n^{\frac{1}{4}}) + 5(n^{\frac{1}{2}} + n) = T(n^{\frac{1}{8}}) + 5(n^{\frac{1}{4}} + n^{\frac{1}{2}} + n)$$
We have a total of $...
- 3
0
votes
2
answers
54
views
Can a program that terminates have a running time of infinity? (Or not have an upper bound)
Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound?
A (non-)...
0
votes
2
answers
64
views
Comparison between big-Ω and ω notations
Example of function f(x) such that it is true that f(x) = Ω(g(x)) but that it is not true that f(x) = ω(g(x))
- 121
0
votes
3
answers
111
views
How do I solve this recurrence equation?
I have to express the solution of the recurrence equation T(n) = T(an) + n where a is a constant, 0 < a < 1, in terms of θ using the iteration method. I am unsure of how I calculate the cost of ...
- 1
1
vote
1
answer
40
views
What's the most scalable solver of this problem?
Consider the following optimisation problem that its size is parameterised by $n$ (width) and $m$ (depth):
Find $w_1, w_2, \ldots, w_n$ that minmises:
$$
\min \Big[w_1x_1^0 + w_2x_2^0 + \ldots + ...
- 115
2
votes
2
answers
88
views
Prove that $O(\sum_{i=0}^{h}{2^i\times(h-i)}) \sim O(2^h)$
I want to prove that, $$\sum_{i=0}^{h}{2^i\times(h-i)} \sim O(2^h).$$
I did come up with the below proof,
$$\sum_{i=0}^{h}{2^i\times(h-i)} \sim O(\sum_{i=0}^{h-1}2^{h-1}) \sim O(h2^h),$$
but as it is ...
- 250
0
votes
0
answers
16
views
least collection of node disjoint paths that cover a given set of vertices
Given a directed graph G (with cycles) with source and target, and a set of interested vertices S.
we want to find a small n collections of vertice-disjoint-paths (path only have common nodes in ...
0
votes
1
answer
39
views
Shell's Increments Worst Case Analysis
My textbook claims the worst-case running time of Shellsort with Shell's increments is $Ω(N^2)$, but this analysis is done when $N = 2^m$ for a positive integer $m$. I see why the proof would work for ...
-3
votes
1
answer
37
views
How do I prove the following relationship between big-theta notation and logarithms?
Prove that:
$\lg (\Theta(n))=\Theta(\lg n)$
- 101
-3
votes
2
answers
85
views
How to find the standard theta notation of this?
Hi i am practising standard theta notation:
How could i find the standard theta notation of the following :
2n + 3n^2(log n)^3 + 2
and
...
- 1
2
votes
1
answer
52
views
Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$
I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under:
$$T(n)=aT(n/\...
- 121
-1
votes
2
answers
86
views
How to prove this because if we consider big-oh than logn^2 <= log n + 5 can never happen if n grows?
f(n) = log n^2; g(n) = log n + 5 => f(n) = Θ (g(n))
I think we can prove this for omega but how can we prove it for Big oh ?
because if we simplify it to logn + logn <= logn +5 => logn<=...
0
votes
0
answers
45
views
Basic Clique Complexity Question
A question in a textbook says, suppose the regular Clique problem, which takes as input a graph G and a natural number k, and returns whether or not G has a clique of size >= k, can be decided in ...
0
votes
4
answers
266
views
What is the lower bound of n factorial
The upper bound of $n!$ is $O(n^n)$. But I am not getting a way to compute the lower bound of n!.
We can write $n! = n\times(n-1)\times(n-2)\times\dots\times 1$. I can easily put all the terms as 1. ...
- 21
0
votes
0
answers
20
views
Order of time complexity in computing $R\sin(2\alpha)$ VS $2R\sin(\alpha)\cos(\alpha)$
I was wondering, in terms of complexity and "precision", what are the differences, if any, netween the computation of
$$2R \sin(\alpha)\cos(\alpha) \qquad \qquad \text{and} \qquad \qquad R\...
- 101
0
votes
0
answers
58
views
asymptotic approximation ratio vs absolute approximation ratio?
I am trying to learn about approximation algorithms. In some research papers, it is mentioned about the absolute approximation ratio. what does the absolute approximation ratio mean? is it different ...
- 123