Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
1
vote
1answer
91 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
169 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
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
43 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 ...
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 ...
7
votes
2answers
123 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\...
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)$" (...
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)) ...
1
vote
2answers
345 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
104 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
61 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 ...
0
votes
3answers
98 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$ ...
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
60 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$ ...
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
25 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?
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 ...
7
votes
4answers
164 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
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 ...
2
votes
1answer
104 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
361 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 ...
3
votes
1answer
105 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 ...
0
votes
2answers
48 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
74 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
56 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
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 $$ $...
3
votes
1answer
169 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
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[...
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
48 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
94 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
70 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
52 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
424 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
420 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
24 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
102 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)$. ...
46
votes
10answers
11k 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)$ ...