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
0 votes
1 answer
12 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)$: ...
user avatar
  • 151
0 votes
1 answer
47 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/...
user avatar
0 votes
2 answers
47 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 ...
user avatar
-1 votes
0 answers
21 views

How can I calculate the computational complexity of an equation composed of $2n$ multiplications and $2nm^2$ additions? [closed]

I want to calculate the computational complexity in term of the big ($\cal O$). My equation is: It composed of 2n multiplications and $2nm^2$ additions. The complexity of this equation is it ${\cal O}...
user avatar
2 votes
3 answers
103 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 ...
user avatar
0 votes
0 answers
29 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 $...
user avatar
0 votes
0 answers
20 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 ...
user avatar
  • 315
-1 votes
0 answers
23 views

Time complexity of a dynamic programming algorithm?

$$a_1,\dots,a_n$$ $$b_1,\dots,b_n$$ are integers bounded in $[-B,B]$ and we want to find a common subset $I\subseteq\{1,\dots,n\}$ such that $$\sum_{i\in I}a_i=\sum_{i\in I}b_i=m.$$ This problem is $...
user avatar
  • 2,822
0 votes
0 answers
23 views

What kind of CNF and DNF are in P [closed]

could anyone help me to prove which languages are in P? I will present my thoughts but I do not know how to go from there. Thank for any help l1 = {L | L is on CNF and is satisfiable} l2 = {L | L is ...
user avatar
  • 103
2 votes
1 answer
73 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 ...
user avatar
  • 205
2 votes
1 answer
71 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))$...
user avatar
  • 1,371
2 votes
2 answers
47 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: $...
user avatar
  • 21
1 vote
1 answer
55 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 ...
user avatar
1 vote
1 answer
67 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 ...
user avatar
1 vote
1 answer
28 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 ...
user avatar
1 vote
0 answers
21 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}$ ...
user avatar
0 votes
2 answers
144 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}$, ...
user avatar
0 votes
1 answer
48 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))$
user avatar
1 vote
1 answer
42 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 ...
user avatar
  • 283
2 votes
2 answers
61 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....
user avatar
  • 235
2 votes
1 answer
34 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 ...
user avatar
  • 23
1 vote
1 answer
132 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$ ...
user avatar
  • 1
3 votes
1 answer
375 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 ...
user avatar
  • 1
0 votes
0 answers
22 views

Peterson's leader election complexity

Giving the Peterson's algorithm for leader election in bidirectional ring: ...
user avatar
0 votes
0 answers
21 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 ...
user avatar
3 votes
2 answers
310 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 ...
user avatar
  • 315
0 votes
1 answer
51 views

Is it faster to use Counting Sort to lexicographically sort characters in a word in Python?

Assuming I have very long words, is it worth it to use Counting Sort with its memory overhead to achieve linear time complexity? I wrote a Python function that sorts the characters in a given string ...
user avatar
  • 1
2 votes
1 answer
50 views

Cost of increasing a binary counter with a starting value n times

Consider a k-bit binary counter and suppose that in the beginning the value of the i-th most significant bit is $b_i$ for each $i = 0, . . . , k − 1$. Let $b = b_0 + 2b_1 +· · · + 2^{k−1} b_{k−1}$. ...
user avatar
1 vote
1 answer
58 views

Why do hash tables have no access/indexing complexity but have $O(1)$ search complexity?

Sources: https://en.wikipedia.org/wiki/Best,_worst_and_average_case https://www.bigocheatsheet.com/ It can be seen that a Hash Table has no access/indexing complexity given the above sources. This ...
user avatar
  • 381
2 votes
1 answer
51 views

Efficient data structure to maintain a set of postal codes and mailbox numbers

A 'person' is represented by a combination of postal code and mailbox number(both are natural numbers) No two postal codes are alike, yet a postal code can contain many different mailboxes. At any ...
user avatar
1 vote
1 answer
29 views

Comparing two functions rate of growth

This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question. Question. Compare the functions $f(n) = \frac{n^2}{\log(n)}$ ...
user avatar
  • 187
1 vote
1 answer
54 views

an O(m+n) algorithm to decide whether a graph can be reduced to a single edge with two vertices

Given B and C operations. B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices. C-operation: When one edge ...
user avatar
0 votes
1 answer
25 views

Sorting optimization to presorted array

I'm looking up the complexities of sorting algorithms. There can be performance harm when the array is already presorted when running certain algorithms. E.g. Using last element as pivot in quick sort ...
user avatar
  • 99
1 vote
1 answer
51 views

A decidable language that can't be decided by a circuit ensemble of linear size

Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
user avatar
0 votes
0 answers
29 views

What is the time complexity of this Java program?

Below is the code. ...
user avatar
4 votes
1 answer
71 views

What are efficient approaches to implement unit propagation in DPLL-based SAT solvers?

I'm trying to decompose deduction steps of DPLL algorithm -- unit propagation and pure literal elimination -- for parallelization. However, I want a baseline and asymptotic analysis to compare to my ...
user avatar
  • 43
2 votes
2 answers
625 views

Doubt about computing running time / time complexity of a function in Python

I am learning about time complexity now, and I am working with BST (Binary Search Trees). This question needs some context and this is a follow up post to this post. Basically, I would like to compute ...
user avatar
  • 187
1 vote
2 answers
47 views

Averege time complexity of open addressing

I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the ...
user avatar
0 votes
0 answers
26 views

Time Complexity of dependent nested loops

I'm recently in to the algorithms and I'm having trouble finding the time complexity(Big-Oh notation) of the following algorithm: ...
user avatar
  • 1
0 votes
1 answer
53 views

Understanding time complexity of algorithm to determine if parenthesis are matching

Both these algorithms determine if all the parenthesis in a string are balanced and properly nested. The first algorithm uses "a constant amount of memory, regardless of the length of the string.&...
user avatar
3 votes
1 answer
67 views

Find the flaw in the 3SAT solver algorithm

I consider decision version of 3SAT problem. Main idea is to find congruent clauses and construct such maximum formula, which satisfiability/truth table won't be changed. In case of unsatisfiable ...
user avatar
1 vote
1 answer
52 views

I need help finding the complexity of an algorithm

i have the following algorithm : j = 1 while j ≤ n do j = 2^j where n is our input and is a non negative integer I found the complexity of the algorithm to be O(1) . Can someone tell me if this is ...
user avatar
1 vote
0 answers
20 views

Algorithm Complexity Question

this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can. I was doing some ...
user avatar
  • 51
1 vote
3 answers
56 views

Recursive algorithm for adding numbers from 1 to n with O(1) time complexity

So I have a recursive algorithm which sums up the numbers from 1 to n plus one (hence the return 1): ...
user avatar
  • 13
1 vote
1 answer
38 views

Newbie needs some explanation on the following code and O-expressed time complexity

I am learning data structures and algorithms currently, and want to understand how the following codes received their O-notations. Code example #1: ...
user avatar
  • 113
1 vote
1 answer
31 views

How to prove that if Eternal Vertex Cover is Polynomial it's possible to detect its vertices and edges

EVG is defined as EVC = { <G,m,k>| G is an undirected graph and there is as et of m edges in G that are covered by at most k nodes} If EVG was decidable in polynomial time how could we find the ...
user avatar
  • 135
1 vote
2 answers
60 views

How to use the step count method correctly for binary search?

I've tried to use the step counting method to get the worst-case time complexity for binary search. But I seem to mess it up, as my final result would be O(n) and ...
user avatar
  • 13
0 votes
2 answers
40 views

Applying the Master's Theorem

Below is a problem I made up and my solution to it. Problem: Given the following recurrence relationship, find $\Theta(T(n))$. $$ T(n) = T\left( \dfrac{n}{2}\right) + n^2 $$ Answer: To solve this ...
user avatar
  • 329
2 votes
3 answers
72 views

Determining Big O of a for loop nested within a while loop

I apologize if this question is a duplicate as i cannot find a similar question in this community forum, please comment the post in which this may be a duplicate of so i can update this post :) Im a ...
user avatar
2 votes
2 answers
37 views

Single-tape $o(n\log n)$ Turing machines and nonregular languages

I am reading Sipser's Introduction to the Theory of Computation, and encountered two propositions: $A = \{0^k1^k \mid k ≥ 0\}$ is nonregular language (pumping lemma). Any language that can be decided ...
user avatar
  • 287

1
2 3 4 5
46