Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

69 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
202 views

Are there master theorems that deal with parameters of the form $n-c$?

While thinking about this question on a recurrence I checked out some stronger master theorems. Unfortunately, they do not seem to apply because terms $\qquad\displaystyle T(n) = \dots + T(n-1) + \...
3
votes
0answers
44 views

Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

I have a graph algorithm that runs in: $$ T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + ...
3
votes
0answers
83 views

Name for function in big O but not in little o?

Let $f(n) = O(g(n))$, but not $f(n) = o(g(n))$. That's a nice property, because it means that we cannot replace $g(n)$ with a substantially smaller function. Is there a name for this choice of $g(n)$? ...
3
votes
1answer
13k views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
3
votes
0answers
1k views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
3
votes
2answers
170 views

Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
2
votes
0answers
473 views

Can factorial be done in O(1) and proof?

The typical way to compute the factorial would take $O(n)$ because it calls itself recursively. However, there are many other ways to compute the factorial function based off the gamma function, ...
2
votes
0answers
21 views

Is variance taken into account when algorithm analysis is performed?

Silly question. I was wondering if the measure of "variance" is taken into account when the analysis of an algorithm is performed (asymptotic). In general best-case,worst-case,average-case are taken ...
2
votes
0answers
191 views

Amortized time complexity of append on a dynamic array that resizes according to geometric base 1.25?

I'm trying to prove that the amortized time complexity of appending to a dynamic array that resizes in accordance with capacity = $N$ to $N+\lceil{\frac{N}{4}}\rceil$ is $O(1)$. I'm assuming that ...
2
votes
0answers
520 views

How to find all paths with n-distance from a node in a graph with cycles?

I have to find all the paths that have some n-distance from a start node. The destination node is not given. It seems that this problem is very hard to solve because in this scenario I am working with ...
2
votes
0answers
35 views

Examples of algorithms with low spacetime complexity

When running a data center, one of the cost metrics you might care about is "ram seconds". For example, an algorithm that holds 1 MB of memory for five minutes consumes 300 million ram seconds. A ...
1
vote
1answer
45 views

Analyzing time complexity of solution in tutorial

Could someone explain time complexity of solution of in this tutorial? I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$. What I figured so far is, for ...
1
vote
0answers
19 views

Useful conditions for proving super polynomial lower bound for some kind of recurrences

Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$ Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
1
vote
0answers
136 views

Approaches for analyzing the work, critical path length and parallelism

I'd like to know where to find references and approaches on how to analyze the work, critical path length and parallelism of algorithms. In particular, for solving the type of homework problems below:...
1
vote
1answer
37 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
1
vote
0answers
22 views

Cuckoo hashing with a stash: how tight are the bounds on the failure probability?

I was reading this very good summary of Cuckoo hashing. It includes a result (page 5) that: A stash of constant sizes reduces the probability of any failure to fall from $\Theta(1/n)$ to $\Theta(...
1
vote
1answer
38 views

Interpretation of an asymptotic notation

Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
1
vote
0answers
81 views

What are the asymptotic bounds (upper bound on time complexity) of the following function?

I am trying to find the upper bound on time complexity of the recursive function defined by the following equation: $$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\...
1
vote
0answers
59 views

Can I say θ(g(n)) is the intersection of Ω(g(n)) and O(g(n))?

Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n). Can I say that θ(g(n)) is the intersection of these two sets? ...
1
vote
0answers
59 views

How to find big-O for an in-place perfect shuffle algorithm

I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
1
vote
0answers
27 views

What is the runtime of Quantum Fourier Sampling

I have seen estimates for the runtime of Shor's Algorithm,, which relies on Quantum Fourier Transformations. What is the runtime of those transformations themselves? Either big-O or more accurate ...
1
vote
0answers
49 views

Can there be functions in o(1) in algorithm analysis?

I saw a similar question to this one here but it's not quite the same as mine: Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$? I've just started a course in data structures and ...
1
vote
0answers
37 views

Order of growth: substitution of monotonically increasing functions

One strategy for ordering the growth of functions involves substitutions when comparing functions using the limit as $n$ goes to infinity comparing two equations using the following rule. $$ \lim_{n\...
1
vote
0answers
67 views

Verifying that $f(x) \leq Cg(x)$ for $x \geq k$

I'm revising for a test and having problems with a past question. It states that $f(x)=5x^2+4x+3$ is $O(x^2)$ and has a series of sub-parts asking if particular values of $C$ and $k$ (e.g., $C=12$, $k=...
1
vote
0answers
250 views

Why do we count the ceils and floors in recursive functions?

When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of $$ T(n) = T(\...
1
vote
0answers
64 views

Divide-and-conquer algorithm to takes a set of itineraries and returns desirable itineraries

I've been given a question that states I will be given a set of itineraries, which are basically tuples in the form (cost, time) for airplane flights. An itinerary dominates another itinerary if its ...
1
vote
0answers
134 views

Asymptotic Analysis of Sum

I want to do an analysis on the sum $ \Sigma_{i=0}^n f(i)$. All that is known about $f(i)$ is that $f(i) \in \Theta (i \log i ) $. How do I do this?
1
vote
0answers
184 views

Is this Summary of Asymptotic Analysis Correct?

I'm one year through both an undergraduate CS and undergraduate math degree, currently studying Big-O analysis, and am trying to develop a "mental checklist" as it were, or a kind of procedural ...
1
vote
0answers
113 views

Proof that $n \log_2 n - n \log_2 e \in \Omega(n \log_2 n)$ (lower bound of sorting algorithms)

Regarding the last step of the proof of the lower bound of comparison based sorting, there is the following implication for the runtime T in my book: $T \ge n \log_2 n - n \log_2 e \implies T \in \...
1
vote
0answers
152 views

Help understanding “little o” notation

I have the following homework problem, with given solution but I do not understand why certain choices in the solution were made as opposed to my own (incorrect) solution and I would like some ...
1
vote
0answers
335 views

Turing Machine that accepts $L=\{a^nb^n | n \geq 1\}$ with at most nlog(n) transitions in 1 tape

I'm having trouble trying to create this machine. I know the answer should go in the way that we always cut in half the number of a's and b's (so the master theorem aplied at $T(n)=T(n/2)+O(n)$ gives ...
1
vote
0answers
51 views

What is the difference between O(n^2) and O(N)[N*O(1)]?

I was reading this article on gperf. In it they claim that the use of nested if statements for parsing command line input of $N$ options ends up making $O(N^2)$ ...
1
vote
0answers
133 views

Algorithm to find min pos difference between two integers in an array

The question I'm faced with: Let $A[1], A[2], ...,A[n]$ be an array containing $n$ very large positive integers. Describe an efficient algorithm to find the minimum positive difference between ...
1
vote
0answers
76 views

Pick algorithm with runtime in O(n) vs. Θ(n) vs. Ω(\log n )

You are given three algorithms, $A$, $B$, and $C$ with the following time complexities in the worst case $O(n)$, $\Theta(n)$, and $\Omega(\log n )$, respectively. Assume that you have to choose ...
1
vote
0answers
102 views

Why does $\sum\limits_{i=0}^{\lg(n)-1} \theta(\frac{n}{2^i}) = \theta(n\lg(n))$?

I'm reading a proof on the time complexity of MergeSort which makes this statement without any justification. I've tried to show it myself but I'm not getting far; these are my steps so far. $\sum\...
1
vote
1answer
59 views

How to find an algorithm's complexity from actual running times

I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of ...
1
vote
1answer
301 views

Solving T(n) = 2T(n/3) + 2 T(2n/3) + n

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed: Recursion tree. We see that $$\begin{align} \sum_{...
0
votes
0answers
11 views

Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
0
votes
0answers
31 views

Deducing $3^f = o(3^g)$ from $f = o(g)$

I really need help solving the following question: Given: $$f(n) = o(g(n))$$ Prove: $$3^{f(n)} = o(3^{g(n)})$$ My attempt: I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0 $. I need to ...
0
votes
0answers
25 views

Calculating the Complexity of a Two Part Algorithm

This is in relation to this post I made. I eventually solved this by the following approach: Take the un-ordered file with all the purchasing data and use the UNIX ...
0
votes
0answers
33 views

Minimization with asymptotic assumption

Given the function $g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with} \left\{\begin{matrix} a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\ b\leq a! \\ c\leq (n-a)! \\ \end{matrix}\right. \Big\}...
0
votes
1answer
25 views

Is this computational complexity of the k-NN (custom distance) correct?

I read on a book that in general k-NN (no optimizations), given $d$ dimensions $n$ examples every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
0
votes
0answers
31 views
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 ...
0
votes
0answers
28 views

In what case would bi-directional BFS have the same asymptotic run time as a regular BFS?

I'm not quite sure when they would have the same asymptotic running time. Would it be if the graph was each node connected to one other node in a line? I know that for a bi-directional BFS to have a ...
0
votes
0answers
80 views

If $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ then is $f(n)=\Theta(g(n))$?

My question is exactly what the title says. If I have that $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ hold, then does $f(n)=\Theta(g(n))$ hold as well? My intuition says that the second part is false, but ...
0
votes
0answers
168 views

How to find lower bound of f(n) for master theorem

I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has. I usually ...
0
votes
0answers
91 views

Big O Notation for Return List is it O(N)?

what is the Big O for Returning List? aka return list (e.g. list=[1,2,...]) is it o(1) or o(n) and is there a good website for average big o for different operations including sorting for simple ...
0
votes
0answers
142 views

Recursion with loop inside

What is the time complexity of this algorithm? I assume that is $O(3^n)$ ...
0
votes
0answers
136 views

Run time analysis of a program with nested for loops

Problem Let's say we are given a program and we want to find an algorithm that analyses its asymptotic complexity. This program can only have two types of statements: ...