Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
0
votes
2answers
24 views
Terminology for worst-case N-complexity on $O(1)$ insert after amortisation
Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews ...
2
votes
2answers
29 views
Are Big-Theta functions asymptotic monotonically non decreasing?
For example, suppose $f(n) = \Theta(n^2)$, then does that mean for any sufficiently large $n$, $f(n) \le f(n+1)$? Is it a general case for all Big-Theta?
1
vote
2answers
49 views
Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?
This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?
2
votes
1answer
100 views
What is the Big-Ω of the following function?
For the following function:
$$
\sum_{n=1}^{2n}x+x^2
$$
It is easy to see the (tightest) Big-Oh is $O(n^3)$, but I am not so sure about the Big-Omega. Here is my attempt:
$$
\sum_{n=1}^{2n}x+x^2
$$
$...
3
votes
1answer
91 views
d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions
Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$.
Then for a ...
4
votes
2answers
63 views
When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$
Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$". Then ...
0
votes
0answers
23 views
Run time analysis of inner loop [duplicate]
What is the run time of the following piece of code in Big-Oh notation? The first loop runs n times in the worst case. But I am having difficulty in finding run time of nested loop which runs V / deno[...
0
votes
0answers
8 views
forming recurrence equations from code
Please could someone help me with understanding how to form recurrence equations when reading code? I'm having some trouble in my class:
...
0
votes
0answers
15 views
Runtime explanation of this function [duplicate]
I am trying to understand the runtime complexity of the below code in terms of n.
I know that it is $Θ(n^{4/3})$, but I don't get why.
I thought the outer loop runs $log(n)$ times, the second one ...
1
vote
1answer
46 views
Is $O(T+\log T)= O(T\log T)$?
Is $O(T+\log T)= O(T\log T)$?
I think this is true but I do not know how to show it mathematically?
Please show it using the definition.
Also, if it is true, is the following true?
$O((T+\log T)^{...
1
vote
1answer
37 views
Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?
I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence ...
1
vote
1answer
61 views
Why $2R\sigma\sqrt{T+logT+1}=\tilde{{O}}(\sigma\sqrt{T})$?
On page 17 on the paper Online Learning with Predictable Sequences, we find a regret of an algorithm equal to
$$
\text{Reg}_T=\frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1)
$$
where $T$ is the ...
2
votes
1answer
46 views
Can I say the two cases of Recursion Tree are always either $\theta{(n)}$ or $\theta({n\log{n}})$
Given positive constants: $c_1, c_2, ..., c_k, c^\prime$, assume that
$T(n) = T(c_1n) + T(c_2n) + ...+ T(c_kn) + c^\prime n$
There are two cases:
$c_1 + c_2 + ...+ c_k < 1$
$c_1 + c_2 + ...+ c_k ...
2
votes
3answers
52 views
How to properly calculate dependent nested loops for big-O [duplicate]
I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, ...
1
vote
2answers
68 views
Show that for any real constants $a$ and $b$, where $b > 0$, $(n + a)^b = \Theta(n^b)$
I'm currently studying growth of function chapter in Introduction to Algorithm. In exercise 3.1-2 the question is:
Show that for any real constants $a$ and $b$, where $b>0$,
$(n + a)^b = \...
0
votes
1answer
21 views
Big O analysis trying to follow a logic
Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."?
I am trying to follow the logic of the solution provide while myself have a different approach. Here is my ...
0
votes
1answer
49 views
Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?
Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?
My attempt:
Lets $f(n)=g(n)=n$, then $f(n).g(n)+h(n)=\Omega(n^2)+\theta(n)=\Omega(n^2)$
But given answer is $O(n)$. ...
43
votes
10answers
10k views
O(·) is not a function, so how can a function be equal to it?
I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.
I understand semantics of it. But $T(n)$ ...
0
votes
0answers
29 views
Lower bound of an iterative algorithm involving a while loop
I have an algorithm that includes a while loop (plus some preceding and subsequent steps that are each run only once).
The least number of iterations required for my algorithm to converge is 1.
...
0
votes
1answer
60 views
How come O(n) + O(logn) = O(logn)
How come O(n) + O(logn) = O(logn)?
When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is ...
0
votes
1answer
45 views
Is this a valid use of big-O notation?
Suppose that $m=O(n^{c+1/2})$ for some real $c>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results.
...
1
vote
1answer
65 views
What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$?
Consider the recurrence
$$
T(n,m) = T(n,m-1) + T(n-1,m) + c,
$$
with base cases $T(n,0) = T(0,m) = 1$.
This is the complexity of a recursive algorithm for the longest common subsequence, I know that ...
1
vote
2answers
71 views
How to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$?
$T(n) = T(n-2)+T(n-3)+2T(n/3)$ and $T(n)=1$ for $n<4$.
I tried to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$ using the recursion tree but it's not clear enough for me to make a guess ...
1
vote
1answer
55 views
Big O space complexity of this isAnagram method
I'm currently debating with some friends what is the Big O space complexity of this isAnagram method:
...
1
vote
1answer
45 views
Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+…+T(\frac{n}{2^k})$
Given is the following recurrence relation:
$T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$
where $k$ is some constant and $n = 2^t$ for some $t\in \mathbb{Z}$.
I'm ...
0
votes
0answers
24 views
Solving Recurrence relation using Master Theorem
There is a recurrence relation like
$T(n)=mT(n/2)+cn^2$
To solve this recurrence relation I am using Master Theorem.
As per master theorem here a = m, b = 2, k=2 ,p=0
So $b^k= 2^2 = 4$
Now, ...
0
votes
0answers
44 views
What's the lower bound of the height of an unbalanced recursion tree?
I don't understand what's going on here. People say, longest path should yield an upper bound of tree height while shortest path should yield a lower bound of tree height. Please take a look at https:/...
4
votes
2answers
107 views
Is “super-exponential” a precise definition of algorithmic complexity?
I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.
For instance, if an algorithm runs for $nC(n-1)$...
0
votes
1answer
22 views
Showing $2^x$ is a lower bound
How do I show that $2^x - x^2 \in \Omega(2^x)$?
Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.
I worked around a bit with ...
0
votes
1answer
22 views
Big O order of a function
I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function 𝑓(𝑛) = 𝑛^2 + 𝑛 log2(𝑛) + log2(𝑛). Show your working.
My answer is O(n^2) ...
1
vote
1answer
43 views
How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
1
vote
2answers
52 views
Is the runtime of binary search big omega of logarithm of n?
My question is that can we say that runtime of the binary search is $\Omega(\log n)$?
I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst ...
1
vote
1answer
48 views
Big O and constants [duplicate]
I've already asked this question on stack overflow, but guys have suggested me to ask my question here.
Let's consider classic big O notation definition (proof link):
The $O(f(n))$ is the set of all ...
0
votes
2answers
31 views
Calculation of Inorder Traversal Complexity
I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
1
vote
1answer
22 views
Big-Oh vs Theta in recurrence tree method
I am solving this problem from here.
The given relation is
$$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$
The solution via recurrence tree method is given as:
The zeroth level has a single node ...
1
vote
1answer
61 views
Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$ [duplicate]
I have the following two functions
$f(n) = n\sqrt n + n \log n$
$\log_{100} n$
And I need to classify them into the followings:
$O(n)$, and/or
$O(n^2)$, and/or
$O(n^3)$, and/or
$O(n^{1.5})$, and/or
...
1
vote
2answers
56 views
Big-O Solving Recurrence Relation by iteration with fractions
I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer ...
1
vote
2answers
79 views
Why is $\dfrac{1}{2}n^2-3n = \Theta(n^2)$?
By definition:
For a given function $g(n)$ we denote by $\Theta(g(n))$ the set functions
$\Theta(g(n))$ = $\{f(n):$ there exists positive constants $c_1, c_2$ and $n_0$ such that $0 \leq c_1g(...
0
votes
0answers
24 views
Does $\lg{(n+1)} \in O(\lg{n})$? [duplicate]
I know this is kind of an ugly notation, so if you prefer: let $f(n) := \lg{(n+1)}$. Does it hold that $f(n) \in O(\lg{n})$?
3
votes
2answers
56 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
116 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$.
0
votes
1answer
28 views
Why is max{n,k}= Ө(n+k) [duplicate]
I saw this relationship in my exercise.
max{n,k}= Ө(n+k)
Could somebody prove it?
1
vote
2answers
46 views
Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How? [duplicate]
Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? If so then how?
1
vote
1answer
17 views
Represent polynomial time complexity as linearythmic
To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, ...
0
votes
1answer
61 views
Show that $T(2^n) = \Theta(3^n)$ [duplicate]
We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n > 1$. We need to show that $T(2^n)=\Theta (3^n)$. How should I approach this question? Any suggestion?
0
votes
1answer
66 views
Big O Notation Simplification in the fraction form
How should I approach this one a(n) = $\frac{n^3}{log^{3}(n)}$. As We can tell that $n^3$ grow much faster than $log^{3}(3)$. All of sudden, not sure what to do, found this [post][1], which is also ...
1
vote
1answer
112 views
Big-O with nested loops and “variables” in the T(n)
So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code:
...
1
vote
1answer
53 views
Introductory explanation of the Big-Oh properties
I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic ...
1
vote
2answers
46 views
How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$
How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ?
Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I ...
1
vote
1answer
23 views
Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?
We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$.
I came up with following proof but i dont know it's correct or not.
$$g = O(f)$$
$$g \le c_1*f $$
$$h \le c_2*f $$
...
