Questions tagged [time-complexity]

The amount of time resources (number of atomic operations or machine steps) required to solve a problem expressed in terms of input size. If your question concerns algorithm analysis, use the [runtime-analysis] tag instead. If your question concerns whether or not a computation will *ever* finish, use the [computability] tag instead. Time-complexity is perhaps the most important sub-topic of complexity theory.

Filter by
Sorted by
Tagged with
1
vote
1answer
37 views

Calculator for time complexity of recursive functions

Is there an online tool that returns the time complexity of recursion functions? For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$. I tried using Wolfram Alpha, but it doesn'...
0
votes
1answer
113 views

Estimating run time of of while loops?

i, sq ← 1, 1 while sq < n for j ← 1 to sq k ← 1 while k ≤ j k ← 2 ∗ k i ← i + 1 sq ← i ∗ i I have Expressed the running ...
1
vote
1answer
64 views

Time complexity and upper and lower bounds

Consider the following algorithm: (the print operation prints a single asterisk; the operation x = 2x doubles the value of the ...
1
vote
1answer
52 views

optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$

I want to optimize an algoritm for calculating $g(n)=\sum^n_{k=2} p(\Omega(k))\Omega(k)$ where $$ p(n) = \begin{cases} 1 &\text{if $n$ is odd} \\ -1 &\text{if $n$ is even} \end{cases}$$ and $...
14
votes
1answer
3k views

Hardness of a problem which is the sum of two NP-Hard problems

Consider the problem of computing an exponential sum over a certain function $g(x)=f(x)+h(x)$, that is computing $$\sum_{x}g(x)=\sum_{x}f(x)+\sum_{x}h(x)$$ now if we know that $\sum_{x}f(x)$ and $\...
0
votes
1answer
38 views

Which of these two functions has a higher order of growth/complexity?

Consider the following functions: $$f(n)=2^{\log^*n} \text{ and } g(n)=\sqrt{2}^{\log{n}}$$ Using $\log{}$ properties I think that $g(n) < f(n)$, since: $f(n)\sim n$, $g(n)\sim n^{\frac{1}{2}}$, ...
0
votes
1answer
141 views

What time complexity is a reachability algorithm?

I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive ...
3
votes
4answers
6k views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
2
votes
0answers
57 views

P/NP - Proof that SAT-TM is NP-complete uses certificate

To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard $$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$ my ...
1
vote
2answers
29 views

Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor

The input: a binary tree and a list $L$ of vertices in that tree. The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of ...
1
vote
0answers
53 views

Most scalable distributed consensus mechanism based on message complexity?

One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity. For example, PBFT message complexity is O(n^2) that ...
1
vote
1answer
42 views

Counting letter frequency in array in O(1) with hash function

I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p'] There are several ways to do this: A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
8
votes
0answers
180 views

Complexity of removing edges to eliminate a perfect matching

Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
21
votes
7answers
5k views

in O(n) time: Find greatest element in set where comparison is not transitive

Title states the question. We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal. Key points: Comparison is not transitive (think rock ...
0
votes
1answer
37 views

Finding the Big-O and Big-Omega bounds of a program

I am asked to select the bounding Big-O and Big-Omega functions of the following program: ...
4
votes
2answers
45 views

Finding which functions are bounded by $O(n^2)$

I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$. $f(n) = \sum_{i=1}^{n} n$ $f(n) = \sum_{i=1}^{n} i$ $f(n) = n + n^2$ $f(n) = 1$ I choose the ...
1
vote
1answer
52 views

Using Subset Sum algorithm $O(n)$ times to find the subset

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
1
vote
1answer
662 views

Is time complexity of the greedy set cover algorithm cubic?

I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements....
1
vote
0answers
32 views

Approximating the Levenshtein distance between two binary strings using the Fast Walsh-Hadamard Transform

I have come up with a simple technique of approximating the Levenshtein distance between two binary strings using the fast Walsh–Hadamard transform: given two binary strings $a,b$ with Walsh–Hadamard ...
0
votes
1answer
15 views

Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation

The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$, The reason for ...
1
vote
1answer
19 views

Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity?

This is a rather well known solution to the $k$-th order statistic problem which requires us to find the $k$-th largest number in an unsorted array with $n$ elements where $1 \leq k \leq n$: ...
1
vote
2answers
75 views

Time complexity of comparing $N$ strings

I would like to double check myself. As I understand time complexity of comparing two strings in the worst case is $O(n)$, where $n$ is the length of the strings (let's say they are equal length). In ...
1
vote
2answers
37 views

Compute average case with best case

is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (...
0
votes
1answer
29 views

How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?

Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $n$ is odd, it sorts using Bubble Sort and for even $n$ it uses Merge Sort. How do we perform ...
0
votes
1answer
44 views

How efficient of this prime sieving algorithm?

I just found there is an old program of mine where I implemented the following prime sieving algorithm: ...
1
vote
1answer
42 views

Asymptotic growth of a series

How we can prove that: $$ \sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?} $$
0
votes
0answers
11 views

It is possible proove the complexity of each query in a Segment Tree to O(log N) with recursion tree

Maybe the title is bad format but, I want to ask if is possible proof the Segment Tree complexity with the recursion tree. In other words I'm making a simple report on segment tree and I want to try ...
1
vote
1answer
43 views

Time complexity of Tsp using DP

this is the recursion formula for problem : C(i,S) = min { d(i,j) + C(j,S-{j}) } In fact, when I tried to implement it as a code, the following code came to my ...
0
votes
0answers
35 views

In-place linear sort of integers, again

I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g. is-this-implementation-of-bucket-sort-considered-in-place is-counting-...
3
votes
2answers
449 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
0
votes
1answer
33 views

Run-time of a summation function and its complexity

I am trying to analyze the running time of the following function: ...
0
votes
2answers
36 views

Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$

I need to prove that the following recurrence relation is $O(5^n)$: $$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$ And $T(n)=\Theta(1)$ for $n\le 9$. I am trying induction, and proving that there ...
3
votes
1answer
44 views

surprizing reducibility and challenge on it

Assume that Problem $A$ is polynomial-time reducible to problem $B$. Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard. Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard. ...
0
votes
1answer
141 views

Analysis of updating vertex and one example?

I see the following image on google: And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should ...
0
votes
1answer
88 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, ...
3
votes
1answer
202 views

“Fuzzy” Chinese Remainder Theorem

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&\equiv a_3 \mod 7 \...
3
votes
0answers
46 views

Bipartite graph projection, with threshold

Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$. The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
0
votes
1answer
47 views

Complexity of generating power sets

Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a ...
0
votes
1answer
33 views

Help with model answer for time complexity

Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n? I tried to write this in python to ...
1
vote
2answers
40 views

How to index a tree to allow efficient search for paths?

By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be ...
2
votes
0answers
23 views

Central Trinomial Coefficients best time complexity

What is the fastest known time complexity for computing central trinomial coefficients? Let $C_n=1,1,3,7,19,51,...$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$. ...
2
votes
1answer
46 views

Intuition on O(number of leaves) for master theorem

I am trying to develop the intuition of the master theorem for the case where $a > b^{d}$ [Case 3] in this video. In the video, they say that since most of the work is done at the leaves, we should ...
3
votes
1answer
6k views

Understanding Expected Running Time of Randomized Algorithms

I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random ...
0
votes
1answer
45 views

Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph

Suppose that we have a complete undirected positive weighted graph $G = \langle V, E\rangle$. What is the most efficient algorithm, in terms of time complexity, to find an MST for $G$? The best prime ...
1
vote
1answer
271 views

CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...
1
vote
1answer
53 views

Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path

Summary: A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain ...
27
votes
2answers
25k views

Why is push_back in C++ vectors constant amortized?

I am learning C++ and noticed that the running time for the push_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is ...
0
votes
1answer
531 views

Modular exponentiation running time

I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student). Is it poly ...
1
vote
1answer
48 views

I don't get why the time complexity of insertion on a linked list is O(1)

I was watching the algoritmhs course by mycodeschool and he said that when we add a new item on a given position the worst case would be $O(n)$. Everywhere I look says insertion is $O(1)$... Now I ...
1
vote
2answers
43 views

What are the units for time complexity graphs?

I often see big-O notation for time complexity algorithms and I see an equation that looks like $O(n) = n\log n$, which naturally generates a graph like the bottom one: I know the x-axis represents ...

1
2
3 4 5
38