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

1,006 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
38 views

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 ...
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 ...
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 ...
43 views

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 ...
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 ...
123 views

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)$?
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 ...
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 ...
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$ ...
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 ...
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$ ...
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 ...
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 ...
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?
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 ...
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 ...
44 views

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 ...
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 ...
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[...
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 ...
48 views

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, ...
420 views