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
2 votes
1 answer
46 views

Simulating nondeterministic RAM with nondeterminstic turing machine

Nondeterminstic RAM is like deterministic RAM with extra instruction “JMAYBE” which nondeterministically jump or continue when executed. According to this paper: An $O(T \log T)$ reduction from RAM ...
0 votes
4 answers
65 views

Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?

So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ...
9 votes
1 answer
1k views

Algorithm for merging arrays while keeping their order

My question is generalizable to arrays of any type but I'll use strings to keep it short. We take a couple of strings as an input. Let's denote them ${S_1,...S_n}$. (Ex: "ABEF" and "CDE&...
  • 93
1 vote
2 answers
82 views

Big O notation simplification from sum

On calculating the convexity of an optimization problem, I am getting a term $O(\sqrt{n+m}(n)^3)$. Here both $m$ and $n$ are parameters. Is there any way I can simplify this term to write it as a ...
0 votes
1 answer
15 views

CNF-SAT time complexity and input processing

Boolean Satisfiability (CNF-SAT) problem in $n$ variables may contain a CNF formula with $O(2^n)$ clauses in the worst case. My question is: Wouldn't a program reading a CNF formula have to ...
  • 113
0 votes
0 answers
56 views

time complexity of radix sort including duplicate keys

imagine that we have an array including n distinct integers in the range of [1,n^6] and we want to sort it by radix sort which uses an auxiliary algorithm with <...
  • 1
-1 votes
1 answer
79 views

What is the time complexity of SLR and LALR parsers?

What is the difference between time complexity of SLR(k) and SLR(1)? and also what about LALR(k) and LALR(1)? How can I calculate time complexity of parsers? I think time complexity of LR(k) is O(n) ...
-2 votes
2 answers
30 views

I need to sort out the theta complexity for lg(n^(1/2)) [closed]

Can you help me find the theta complexity for lg(n^(1/2))?
1 vote
0 answers
43 views

algorithm with linear time complexity

We say that if an algorithm takes p time for an input size of n (here, p is a polynomial in n, and the degree of p is y), then the algorithm's complexity is O(n^y). In the image, when n is very large ...
1 vote
2 answers
537 views

What does O( n^{1+o(1)} ) mean

The latest development in solving the max-flow problem promises a ${\displaystyle O(E^{1+o(1)}\log U)}$ solution. What does it mean, this $O(n^{1+o(1)})$-complexity?
  • 28.5k
4 votes
1 answer
101 views

Can almost equal partition problem be solved in polynomial time?

Given a list of positive integers with sum $s$, decide if there is a subset with sum $0.5s$. This is the well-known PARTITION problem, which is NP-hard. What about the following: Given a list of ...
1 vote
1 answer
26 views

Sampling unique records from a large dataframe

Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe? Some sort of sampling algorithm?
1 vote
2 answers
169 views

Is the complexity of this two-sum binary search algorithm $O(\lg n)$ or $O((\lg n)^2)$?

This algorithm solves the Two-Sum problem$^1$ assuming that the input array/list is sorted. ...
  • 115
5 votes
2 answers
98 views

The optimal complexity of intersecting a line with a convex hull of a set of points in 2d

The problem: in 2d, given a line and an unordered set of $N$ points with real coordinates, find the intersection between the line and the convex hull of the points. Clearly, one can explicitly ...
  • 83
0 votes
1 answer
111 views

Disjoint Set union complexity when makesets, unions and finds follow a certain order

Consider an arbitrary sequence of $m$ MAKESET operations, followed by $u$ UNION operations, followed by $f$ FIND operations, and let $n = m + u + f$ in a disjoint set union data structure. Prove that ...
0 votes
0 answers
57 views

Time complexity of negating a CNF formula

Suppose i have a CNF formula. If i negate the CNF formula, then i obtain DNF formula. However, i can't find anywhere on internet that mention the time complexity. What is the time complexity of ...
  • 103
0 votes
0 answers
70 views

Big O notation for halving substrings in a string of length n

I am trying to do some runtime analysis on a problem, but get stuck on some details. I have a string $P$ of length $n$, where I am allowed to halve substrings inside of it and keep the right-hand side ...
  • 1
1 vote
1 answer
73 views

Would this be the correct time complexity?

I'm currently working on an exercise that has made me ponder for a bit. The following exercise is from the 6th Edition of Data Structures and Algorithms in Java: An inverted file is a critical data ...
  • 219
1 vote
1 answer
641 views

What is the amortized cost of pulling top K elements from a priority queue?

To pop an element off of a priority queue, the worst-case complexity is: O(logN) where N is the number of elements. Now if you do K pop operations on the priority ...
  • 111
0 votes
1 answer
106 views

Time-complexity of evaluating a CNF formula

Given a Boolean formula over $n$ variables in CNF and a partial assignment to it, all the algorithms I can think of to evaluate the assignment run in time $\Theta(n^2)$. Is it possible to do it in $O(...
1 vote
4 answers
465 views

Stable sort an array with k distinct elements, each appearing double the times the previous one appears

I've started with thinking of a bucket sort/radix sort variation, only to be disproved by a colleague. Here's the problem: Given an array with $k$ distinct elements, it is known that the smallest ...
  • 109
1 vote
1 answer
178 views

Limited tapes-version TM for pair sum

In the problem of pair-sum we are given a multiset $A$ and a number $\alpha$. We are asked to find whether there is a pair ($2$ numbers) of $A$ s.t. their sum is $\alpha$. Here all numbers are small/...
0 votes
0 answers
11 views

Are there any examples of quantum simulator programs than run faster or use less memory than similarly idiomatic classical analogs?

I'm curious if there are any examples of programs written for quantum simulators that are more performant (time or memory) than their classical analogs. I acknowledge that at simulator runtime these ...
0 votes
0 answers
17 views

Learner Algorithm Time & Sample Complexity

Let $X=R^{2}$. Let $u=\left(\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ w=\left(-\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ v=\left(0,1\right)$ and $C=H=\left\{h\left(r\right)=\left\{\left(x_{1},x_{2\ }\...
0 votes
0 answers
56 views

Complexity of finding the kth smallest element of all the elements in two order statistics binary search trees

What is the time complexity of finding the kth smallest element of all the elements in two order statistics binary search trees? An order statistics tree is a binary search tree where the size of a ...
0 votes
0 answers
41 views

How will changing the splitting point in merge sort affect the algorithm and its time complexity

Everyone knows that merge sort will continuously divide the array into halves until they are small enough to (like 2 elements per block or so) be able to be sorted quickly, hence its time complexity ...
0 votes
0 answers
22 views

Are there computational complexity results for generative adversarial networks?

First time posting on here; if this question is too rough I would appreciate if you could point me to a stackexchange forum where this question may be a better fit. Generative adversarial networks (...
0 votes
0 answers
68 views

Modification on Boyer Moore Algorithm to find an element that occurs more than n/3 times

Given an array of numbers with length $n=3^k$, we try to find an element that occurs more than $\frac{n}{3}$ times. So work as follow: We divide the array into 3 parts of equal length. Find ...
  • 1
1 vote
1 answer
319 views

Time Complexity of ${n \choose k}$

I want to know the time complexity of specifically calculating ${n \choose k}$ where it is defined as $$ {n \choose k} = \frac{n!}{k!(n-k)!}. $$ If the factorial function is recursive $O(n)$: ...
  • 161
0 votes
1 answer
74 views

Does a constant time compression algorithm proves that P=NP?

Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP? That is, an algorithm that doesn't rely on patterns/...
0 votes
2 answers
55 views

A little confusion with Big Theta time complexity

I came across one Big Theta expression: Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function ...
2 votes
3 answers
184 views

Find the smallest difference between two numbers in a DS in O(1) time

I got an assignment to create a new data structure, with the following rules: Init - O(1). Insert x - O(log$_2$n). Delete x - O(log$_2$n). Search for x- O(log$_2$n). Find max difference between two ...
0 votes
0 answers
53 views

Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized

Given a graph with $V$ vertices and $k$, find a set $K$ of $k$ vertices of $G$. Let $c(v)$ be the distance (in BFS-like) of the vertex $v \in V$ to the closest vertex $u \in K$. How to choose the set $...
0 votes
0 answers
25 views

Time complexity of find() operation for a Merge-Find Set

Given a Merge-Find Set implemented using a set of linked-lists, my professor says that the time complexity of find() operation is O(1). Each element of the lists ...
  • 337
2 votes
1 answer
82 views

Is $m \log^2 n$ complexity too much?

I have been struggling for a few hours in terms of finding the right solution for the following problem: Suppose we have a file that contains integers where each represents a user of a service. By ...
  • 219
2 votes
2 answers
111 views

Exponential Time Hypothesis and the input size vs number of variables

According to Exponential Time Hypothesis there does not exist a deterministic algorithm to solve SAT over $V$ variables in time $o(2^V)$. However, let's say the number of literals $n = \omega(poly(V))$...
  • 1,393
2 votes
2 answers
50 views

Delete consecutive characters and add zeros at the end with a restriction

Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character, The restrictions: $...
  • 21
1 vote
1 answer
142 views

Time Complexity of Exponentiation Operation as per RAM Model of Computation

Now, $\color{blue}{\text{Exponentiation}}$ is defined as Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and ...
1 vote
1 answer
107 views

Time complexity analysis for dynamic programming using memoization

I am trying to figure out the time complexity for "Regular Expression Matching" problem. Problem statement is simple, only meta characters allowed are '.' and '*'. Actual problem statement ...
1 vote
1 answer
39 views

Complexity of finding $d$ largest eigenvectors of a symmetric matrix

I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ...
  • 123
0 votes
0 answers
79 views

Worst case lower bound of the general number guessing problem

I have the following problem: Let Alice and Bob be two people playing games. Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
0 votes
2 answers
196 views

Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity

An accountant in a big firm would like to find the median of the salaries of all employees. The data they received is a list of size n containing the tuples $\left\{s_{i\ },f_{i\ }\right\}_{i=1}^{n}$, ...
0 votes
1 answer
52 views

equivalency of some facts in $O$ notation

I misunderstanding about some logarithm property in algorithm course: is it correct that we say following three term is equivalent? $O(\log a + \log b)$ $O(\log (ab))$ $O(\log (a+b))$
1 vote
1 answer
54 views

Subdivide a graph into non-crossing triangles with maximum edge weight

Let $G=(V,E)$ be a complete finite graph with the vertices arranged in a circle. Each edge has a nonnegative weight, and we would like to find an efficient algorithm to find a subgraph of maximum ...
  • 293
2 votes
2 answers
73 views

What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?

I know that retrieving an item in a collection can be done in $O(1)$ time(on average) using hash tables. I would like to know if there is an algorithm that could be as performance without using arrays....
  • 235
2 votes
1 answer
41 views

Complexity of a restricted SAT problem

I am wondering about the complexity of the following SAT related problem: Given a CNF with $n$ clauses containing exactly $k$ literals with the following properties: The intersection of any pair of ...
  • 23
1 vote
1 answer
150 views

Find a path with given weight and the minimum number of edges on a tree

Suppose given a positively-weighted tree $T=(V,E,w)$ and $k\in \mathbb{N}$, where $|V|=n$, the weight function $w:E\to\mathbb{N}$, and each node has degree at most $3$. How we can find a path on $T$ ...
  • 1
4 votes
1 answer
600 views

Count the number of intersections of n chords of a circle in O(n log n) time

Suppose you are given two sets $\{p_1, p_2,\dots , p_n\}$ and $\{q_1, q_2,\dots , q_n\}$ of $n$ points on the unit circle. Each point $p_i$ is connected to $q_i$ by a line segment. How could we count ...
  • 1
0 votes
0 answers
36 views

The total number of nodes and the height of a ternary search tree

So I need to insert into the ternary search tree (TST) about N strings. Each string is a unique ID "consists of 10 letters, the first 3 are upper case letters and the last 7 are digits" for ...
3 votes
2 answers
366 views

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Given the recurrence $$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$ My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
  • 337

1 2
3
4 5
49