Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,001
questions
1
vote
1answer
39 views
Asymptotic complexity of function with two Input variables
Suppose I have a function with two input below.
$f(m,n) = \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000$.
Is it safe to say that $f(m,n)$ is $\mathcal{O}(m \log n)$, or is it $\mathcal{O}(n^...
-2
votes
2answers
109 views
How to solve equations using big Θ [duplicate]
How would I prove that the statement
$10n^3+3n=Θ(n^3)$
is true/false?
0
votes
2answers
289 views
proving big theta [duplicate]
How would I tackle this equation?
$$10n^3 +3n = \Theta(n^3)$$
I know I have to solve Big $O$ and Big $\Omega$ but have no idea how to do this.
I got as far as
$$10n^3+3n \leq c_1n^3$$
$$0 \leq ...
2
votes
1answer
87 views
Can all $O(n)$ problems be solved without nested loops?
There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a ...
0
votes
3answers
94 views
What is the asymptotic complexity of the following code snippet?
for (i = 2; i < n; i = i * i) {
for (j = 1; j < i / 2; j = j + 1) {
sum = sum + 1;
}
}
I know that the outer loop can run for a maximum of $n^2$ ...
4
votes
2answers
65 views
Order Mistake Definition in CLRS
On page 53 or CLRS it has said :
We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function $g(n,m)$, we denote ...
1
vote
1answer
24 views
Minimum number of tree operations to normalize a labeled tree
Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many ...
1
vote
1answer
90 views
To check if a chain with $n$ links can be “folded” into a size at most $L$
Given a chain of $n$ links, each of length $a_1, a_2,..a_n$, where each $a_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists ...
2
votes
2answers
24 views
Maximum Changes that don't Break the Build
Let's say I have a set of changes, e.g. replacing foo with bar in a codebase, how do I programmatically discover the largest set ...
2
votes
1answer
158 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 ...
2
votes
2answers
44 views
Why is $\binom{n}{f}^g=O(n^{fg})$ true?
Why is it true? I understand why $n^g$ but how does the $f$ get there in the power??
I believe from the context that it's not just that $\binom{n}{f}^g$ is strictly smaller than $n^{f g}$, but rather ...
0
votes
1answer
38 views
Have I proved $\sum_{i=1}^{\lg n} 2^{i-1} = \Theta(n\lg n)$?
I have an exercise problem and don't know why its answer is like this.
$$ \sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(2^{\lg n}) = \Theta(n). $$
Regarding this equation, I think it would be,
$$ \sum_{i=1}...
-1
votes
1answer
27 views
Is $\sum_{i=1}^n i \in \Theta(n^2)$?
Please help me understand on how to prove or disprove the following. I have been practicing and doing others which are ok, but with this sum, it is rather confusing.
$$\sum_{i=1}^n i \in \Theta(n^2)...
0
votes
0answers
16 views
Solve Recurrence $T(n) = T(pn) + T((1-p)n) + \Theta(n)$ [duplicate]
For $0 < p < 1$, how can you solve the recurrence $$T(n) = T(pn) + T((1-p)n) + \Theta(n)$$ using the substitution method. My guess is $T(n) = O(n \log n)$, but plugging this guess in leads to a ...
0
votes
0answers
28 views
Can the average case of an algorithm be $O(n \log n)$ if the best case running time of an algorithm is $\Theta(n \log n)$? [duplicate]
Let us suppose the best case running time of an algorithm is $\Theta(n \log n)$. Can the average case run time of the algorithm be $O(n \log n)$? Since $O(n\log n)$ would imply the value going even ...
0
votes
1answer
89 views
What time complexity (big o) is this specific web crawler implementation?
Note: this question was marked as a duplicate in favor of this question/answer which attempts to provide a generic formula for translating code to mathematics.
Unfortunately I didn't find that ...
0
votes
2answers
55 views
Showing that $\lg(n!)$ is or is not $o(\lg(n^n))$ and $\omega(\lg(n^n))$
My instructor assigned a problem that asks us to determine which asymptotic bounds apply to a certain $f(n)$ for a certain $g(n)$, in my case $f(n) = \lg(n!)$ and $g(n) = \lg(n^n)$. For clarity, the ...
1
vote
1answer
41 views
Solving the recurrence $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $
I need to solve the following recurrence relation: $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $. Obviously, the master theorem doesn't apply here so I was using the substitution method. I used $x=\log n$ and $F(x)...
1
vote
1answer
15 views
Algorithm notation between two functions [duplicate]
I have two functions,
$$ f = n^{1.6} $$
$$ g = n^{1.5} $$
I thought this is $ f=\theta(g) $, since $ f $ is asymptotically tight bound of $ g $, if $ n $ goes to infinity. However, the answer is $ f ...
2
votes
1answer
48 views
All pair shortest path in a tripartite graph
I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
1
vote
0answers
33 views
Prove that the upper bound for T(n)=T(an)+T(bn)+O(n) is O(n) [duplicate]
While learning Median of Medians algorithm i came across the following lemma ;
"For any recurrence of the form $T(n)<=T(an)+T(bn)+O(n) $,
if $(a+b)<1$ the reccurence will solve to $O(n)$"
(...
7
votes
2answers
115 views
The recursion $T(n) = T(n/2)+T(n/3)+n$
I'm looking at the reccurrence
$$T(n) = T(n/2) + T(n/3) + n,$$
which describes the running time of some unspecified algorithm (base cases are not supplied).
Using induction, I found that $T(n) = O(n\...
2
votes
1answer
39 views
Solving T(n) = T(n-1)*T(n-2)
So, this is how I solved
$\displaystyle
T(n-1) \approx{} T(n-2)
$
$\displaystyle
T(n) = T(n-1)^2
$
Add log in both sides
$\displaystyle
log(T(n)) = 2log(T(n-1))
...
2
votes
1answer
367 views
What is the relationship/difference between best/worse/expected case and big O/omega/theta? [duplicate]
In the big O section of Cracking the Coding Interview 6th edition, I read the following.
...
1
vote
2answers
334 views
Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?
Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation always have a time complexity of $O(n^2)$?
4
votes
1answer
100 views
Why integer division is of equal complexity as multiplication
I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to ...
-1
votes
1answer
60 views
Analyzing asymptotic notation $\sqrt n = O(\log^2 n)$
I am trying to determine whether $f(n) = \sqrt n$ is in $O(g(n))$, $\Omega(g(n))$, or $\Theta(g(n))$ where $g(n) = \log^2 n$.
The answer says that only $f(n) = \Omega(g(n))$ is correct, but why isn't ...
1
vote
1answer
41 views
Asymptotic relation between n! and (n+1)!
I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
1
vote
1answer
58 views
Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$
I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method:
$$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$
First, we have:
$a = 10,\ b = 2$ ...
3
votes
2answers
5k views
If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))?
I guess this is true, because log is a strictly increasing function, but how do I prove it formally?
I tried something like:
Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in \...
0
votes
1answer
27 views
Algorithm comparison
I am learning Big O and Big theta notation and confused the certain case.
I have two functions,
function 1(f1)
$$ n * n^{1/2} $$
function 2(f2)
$$ 1.001^n $$
in smaller cases (10,000) f1 is much ...
0
votes
0answers
23 views
The applicability of the Master Theorem and calculation of asymptotic limits
Given the following recursive equation
$T(n)=3T(\dfrac{n}{8})+ Θ(n^{1/3})$
I want to know how to explain the applicability of the Master theorem in a rigorous
way and what means asymtotic limits of ...
2
votes
2answers
72 views
Meaning of $ e^x = 1 + x + Θ(x^2)$?
In the CLRS chapter 3: When $x → 0$, the approximation of $e^x$ by $1+x$ is quite good:
$$e^x = 1 + x + Θ(x^2).$$
How is it to be interpreted, what is the role of asymptotic notation here?
7
votes
4answers
162 views
What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
1
vote
2answers
76 views
Running Time of Sorting Algorithm
Determine the asymptotic running time of the sorting algorithm maxSort.
Algorithm maxSort(A)
Input: An integer array A
Output: Array A sorted in non-decreasing order
...
1
vote
1answer
44 views
Are the following Big Oh Notations equivalent?
In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent.
$\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$
$\...
3
votes
2answers
190 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
102 views
Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue
we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|).
Now let's modify ...
2
votes
1answer
99 views
Running Time for Finding Maximum
Consider the algorithm findMax that finds the maximum entry in an integer array.
Algorithm findMax($A$)
Input: An integer array $A$
Output: The maximum entry of $A$
...
0
votes
2answers
335 views
How to calculate time complexity of a randomized search algorithm?
Example: Finding an element from a sorted array
Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the ...
1
vote
1answer
18 views
Bounds on “well dispersed” sparse matrices
Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is ...
1
vote
1answer
97 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:
...
0
votes
2answers
47 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
73 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
55 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?
3
votes
1answer
166 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
1answer
81 views
A totally-ordered set of functions
When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well ...
2
votes
1answer
103 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
$$
$...
4
votes
2answers
82 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[...
