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
43 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 ...
0
votes
1answer
36 views

Operations with Asymptotic Notations

I am wondering is anyone has something like a cheatsheet with all the operations between BigO(n), Theta(n), BigOmega(n), littleO(n), littleOmega(n). For example, this is something I don't know how to ...
-3
votes
0answers
32 views

What's the time complexity of those functions? And Why?

int f(int n) { if (n <= 1) return n; return 2*f(n-1); } int g(int n) { if (n <= 1) return n; return g(n-1) + g(n-1); }
0
votes
1answer
35 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}}$, ...
13
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 $\...
2
votes
0answers
54 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
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)$ ...
0
votes
1answer
34 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
41 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
votes
0answers
20 views

What's the asymptotically lower bound of time complexity that iterate all r combinations of an arraylist length n?

Below is an example of algorithms that iterate all r combinations of an ArrayList of n elements. It read/write ...
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
18 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$: ...
0
votes
1answer
26 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 ...
1
vote
1answer
40 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{?} $$
1
vote
2answers
35 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 (...
1
vote
2answers
69 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 ...
0
votes
0answers
10 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
0answers
33 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-...
2
votes
1answer
26 views

Clarifying the definition of reduction with regards to NP-complete problems

In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a ...
1
vote
0answers
30 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
2answers
35 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 ...
2
votes
1answer
36 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
46 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 $...
3
votes
0answers
41 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 ...
2
votes
0answers
22 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
45 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 ...
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 ...
1
vote
1answer
51 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 ...
1
vote
1answer
44 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
votes
0answers
17 views

What is the difference between Theta notation and Big O notation and Omega? [duplicate]

Why we need to used Theta notation? I read lots of online articles about asymptotic notation and analysing but I can't understand the difference between Theta notation and Big O and Omega. Can anyone ...
1
vote
1answer
45 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
42 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
vote
1answer
25 views

Time complexity of a recursive function which generates all combinations of an array

The following function getCombinations, is a recursive function that can be used to generate all combinations of an array. How exactly can we find the time complexity of this function? I would ...
0
votes
1answer
56 views

How to calculate O-Notation?

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; What I would like to ask, if there is a certain way to find out O-Notation? Actually ...
2
votes
1answer
94 views

Comparing two algorithms for all-pairs shortest paths

I read in my notes: If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, ...
0
votes
0answers
40 views

what is the time complexity of Leiden Algorithm?

I am not able to find out the time complexity of the Leiden Algorithm. Can anyone here help me? https://doi.org/10.1038/s41598-019-41695-z.
0
votes
1answer
29 views

Run-time of a summation function and its complexity

I am trying to analyze the running time of the following function: ...
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
33 views

Runtime Complexity of Memoization

I am struggling to analyze the runtime complexity of the following algorithm formally: Given a string s and a dictionary of words dict(wordDict), add spaces in s to construct a sentence where each ...
2
votes
1answer
36 views

Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$

Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$. Hint: Assume that there is an equality, show that this implies $\mathsf{DTIME}(n^{\log n})\subseteq \mathsf{P}$ via a ...
2
votes
1answer
41 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
1answer
40 views

Find amount of elements greater then number k in a BST

I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K. I found it problematic as there are elements which might be greater then K but wont ...
1
vote
1answer
32 views

Bit complexity of $n$-th Fibonacci number using matrix multiplication

I want to find the bit complexity of finding the $n$-th Fibonacci number using the matrix multiplication method. I know that it has complexity $O(\log n)$ if we assume that the standard operations ...
1
vote
0answers
23 views

Connection between convergence complexity of gradient descent and complexity of exactly solving convex program?

Let $f: \mathbb{R}^n \to \mathbb{R}$ be a convex function. Let $V \subseteq \mathbb{R}$ be some closed convex set. Consider the following convex minimization problem: \begin{align} \min_{\mathbf{x} \...
0
votes
1answer
14 views

What is the time complexity of the original Otsu's method?

I'm trying to give a general comparison of the time complexities of various thresholding algorithms. I have not taken an algorithms course yet, so please forgive any misunderstandings. Otsu's method ...
1
vote
0answers
15 views

Different definitions of Exponential Time Hypothesis

I am reading basics of Exponential Time Hypothesis (ETH). There are two statements for it: Statement 1 There exists no $2^{o(n)}$ algorithm for $3$-SAT, where $n$ is the number of variables. Statement ...
3
votes
0answers
18 views

Spanning hypertree which connects the vertices as slowly as possible

I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
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 ...
0
votes
1answer
36 views

An algorithem for finding the number of primes of the form 4k+3 under some n

I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 ...

1
2 3 4 5
38