# 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.

2,406 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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
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 ...
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
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 <...
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) ...
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
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
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
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
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
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
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
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 ...
• 379
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
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
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
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
106 views

• 221
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 ...
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 ...
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 (...
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 vote
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
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/...
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 ...
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 ...
53 views

• 21
1 vote
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 ...
• 239
1 vote
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
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
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}$ ...
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}$, ...
• 221
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
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
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
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
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$ ...
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 ...
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 ...