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
218 views

Finding asymptotic time complexity

So I'm studying for a midterm and my professor put out a sample exam with the answers, and I'm stuck on one of the questions. The answer is Big-O(n^2 log n) Could ...
2
votes
2answers
189 views

Deriving the exact number of execution times

So I'm studying for my data structures midterm and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions. Here's a screen cap: The ...
4
votes
3answers
189 views

Using a proof-of-work system to discourage piracy or encourage donations

Background A proof-of-work system allows one peer to prove to another peer that a certain amount of computational effort was performed. In a network setting this can be used to throttle peer requests ...
13
votes
4answers
44k views

Complexity of recursive Fibonacci algorithm

Using the following recursive Fibonacci algorithm: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) If I input ...
3
votes
1answer
2k views

Complexity of a recursive bignum multiplication algorithm

We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little. The exercise ...
0
votes
0answers
82 views

How to calculate Complexity Time O()? [duplicate]

Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was. I can solve basic problems, but whenever the problem ...
11
votes
1answer
2k views

NTIME(f) subset of DSPACE(f)

As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$? Can anyone point me to a proof or outline it here? Thanks!
21
votes
3answers
1k views

Do functions with slower growth than inverse Ackermann appear in runtime bounds?

Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant ...
7
votes
2answers
894 views

Machines in P undecidable?

Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial ...
2
votes
1answer
434 views

Finding asymptotically tight bounds $\Theta$ of two procedures

I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this: ...
4
votes
1answer
664 views

Is the DPLL algorithm complexity in terms of # of clauses or # of variables?

I'm a bit confused how worst case complexity is estimated for the DPLL algorithm. Is it in terms of number of clauses, number of variables, or something else?
2
votes
1answer
106 views

Calculate the number of elements after multiplying/adding two polynomials

Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial ...
7
votes
2answers
2k views

Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes). The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s ...
0
votes
2answers
204 views

Worst-case time algorithm?...which one is faster?

Imagine that an algorithm A runs in worst-case time $f(n)$ and that algorithm B runs in worst-case time $g(n)$. Answer either yes, no, or can’t tell and could you explain me why? Is A more faster ...
5
votes
0answers
707 views

Time complexity of finding the largest factor of a number (using a specific oracle)

My question is related to this question posted on math.SE: Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper ...
6
votes
1answer
409 views

Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?

When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, ...
7
votes
4answers
537 views

Does the time complexity of a problem change with encoding of the problem?

Suppose I have a decision problem $D$ and I encode it to a language $L \subset \{0,1\}^*$. Now, I can also encode it to a different language $L'$. Is there any theorem relating the time complexity of ...
41
votes
3answers
74k views

What exactly is polynomial time? [duplicate]

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
6
votes
1answer
1k views

What linked list data structure adjustments would give me fast random lookup?

I am presently using an doubly linked list (C++ std::list) to hold a bunch of records that each have a unique integer identifier. The linked list is created in ...
1
vote
1answer
14k views

What does a polynomial time reduction mean?

I am having a little trouble understanding what is meant by a poly-time reduction. Suppose I have two algorithms $A$ and $B$ and then I say that $A$ is reducible to $B$. Does polytime reduction mean ...
1
vote
1answer
276 views

Computing 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time

I've constructed an algorithm that solves the 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time. I'm new to algorithms and was wondering how good is my running time? Googling didn't help. thanks..
7
votes
1answer
10k views

Checking Feasibility of Linear Program in Polynomial Time

Given a linear system of the form: $$\begin{array}{c} x_r = a \quad x_j = b \\ c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\ x_1+x_2 + x_3 + \ldots + x_n = k\\ 0 \le a,b,x_1,x_2,x_3...x_n \le 1\\ k \ge 0 \...
5
votes
3answers
2k views

Store and sort a large number of 64-bit integers

I have about $500000000$, $64$-bit integers, so these numbers are very large. I want to sort them as quickly as possible. I have couple of questions: What data structure do you suggest for storing ...
3
votes
2answers
143 views

Is there an algorithm which can compute every algorithm's time complexity?

I think of an algorithm which computes the time complexity. It would be great if a code editor could compute the time complexity of the selected lines and even compare two pieces of codes in order to ...
1
vote
1answer
181 views

Deciding between two algorithms with similar runtime in two parameters

Let's say I have a problem which depends on two variables, $m$ and $n$. I also have two algorithms for solving the problem. How do I decide which algorithm to use? For example, say I have an array ...
3
votes
1answer
14k views

Time complexity and space complexity in recursive algorithm

...
5
votes
2answers
171 views

A hard $n$-fold integral

Consider the $n$-fold integral $$ J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\theta_n\ldots d\theta_2 d\theta_1 $$ whose intervals are defined by $$ \begin{align} I_1 = ...
7
votes
2answers
1k views

Quantum computers, parallel computing and exponential time

I've read that quantum computers can solve 'certain problems' exponentially better than classical computers. As I think I understand it, it's NOT the same to say that quantum computers take any ...
6
votes
1answer
557 views

Why don't we emphasize "length of input string" when considering time complexity of sorting algorithms?

The knapsack problem is $O(c\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$. However, why don't we ...
1
vote
0answers
34 views

Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
0
votes
1answer
513 views

Time complexity of mutually recursive functions

Suppose I have two mutually recursive functions like this: ...
6
votes
3answers
4k views

What's better for an algorithm complexity, O(log n) or amortized O(log n)?

Some context: I'm to write a program that sorts the lines of a file in C for Linux. Since I have to read all lines of the file (fgets() for example) I'm thinking ...
2
votes
1answer
964 views

Behavior of different multiplied and added time complexities

Θ - Tightly bound O - Upper bound Ω - Lower bound I understand that for addition, the max asymptotic value is taken, for example... if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 + ƒ2 = O(max(ƒ1, ...
2
votes
1answer
109 views

Is the following langauge in $P$ or $NPC$

Assuming $P \neq NP$ Is the following langauge in $P$ or $NPC$: $L=\{\langle\phi\rangle\mid\phi$ is a 3CNF formula with an assignment satisfying at least half of the clauses$\}$ The first thing I ...
14
votes
1answer
267 views

Are runtime bounds decidable for anything nontrivial?

Problem  Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$? Is the above problem decidable for some ...
-2
votes
1answer
92 views

Complexity of a hash tables with balanced trees in the buckets

If I use a balanced tree instead of lists in a hash table implementation, and also after initializing my table I don't enlarge nor reduce the size of the table, what would be the worst case complexity?...
-2
votes
3answers
1k views

Does reachability belong to P?

Reachability is defined as follows: a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$? Is it possible to write a polynomial time algorithm for it? ...
2
votes
1answer
74 views

Complexity of $Ax\geq 0$

May be it's a stupid question (sorry if it's the case). What is the complexity the decision problem: Input: $A\in\mathcal{M}_{n,m}(\mathbb{Z})$ does there exists $x\in\mathbb{N}^n,x>0$ such that ...
7
votes
0answers
162 views

Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
4
votes
1answer
1k views

Lower-bound complexities for finding common elements between two unsorted arrays

I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are ...
6
votes
2answers
558 views

Modeling the problem of finding all stable sets of an argumentation framework as SAT

As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form. Problem: Find all stable sets ...
3
votes
1answer
5k views

Confusion related to time complexity of dynamic programming algorithm for knapsack problem

I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming I didn't get how the time complexity of the algorithm came out to be $O(nV^...
8
votes
1answer
265 views

NEXP = Σ$_2$ ⟹ NEXP = MA?

Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds? (The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} \...
2
votes
1answer
5k views

Time complexity in Big O notation for Harmonic series with first k terms missing

Firstly, let's suppose there exists an algorithm where $i$ iterates from $1$ to $n$, spending $\frac{n^2}{i}$ time in each iteration. Thanks to the well known $O(\log n)$ upper bound for the Harmonic ...
2
votes
2answers
1k views

A Problem on Time Complexity of Algorithms

For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time? By verifying, I mean that given a candidate solution $y$, we can ...
2
votes
2answers
133 views

Why don't we scale the cost of memory access when analyzing runtime of algorithms?

Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size ...
2
votes
0answers
170 views

Complexity of finding a subset of vertices within distance k of each other, given a set of vertices

I am trying to understand an algorithm presented in Using Stable Communities for Maximizing Modularity by S. Srinivasan and S. Bhowmick, along with its complexity results. (The complete algorithm is ...
0
votes
2answers
673 views

Algorithm analysis question in growth of functions

How would I solve the following. An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500? Can anyone help me ...
5
votes
2answers
1k views

Is the problem of evaluating a boolean formula on a given assignment P-complete?

I know that the CIRCUIT VALUE problem is P-complete. In the CIRCUIT VALUE problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given ...
1
vote
3answers
6k views

Can all permutations of a set or string be generated in O(n log n) time?

I was looking over this question requesting an algorithm to generate all permutations of a given string. A comment in the answer caught my eye: It might seem that it can take O(n) time per ...