the amount of time resources (number of atomic operations or machine steps) required to solve a problem or run an algorithm with respect to the input size.

learn more… | top users | synonyms

1
vote
0answers
13 views

Analysis of Weighted Quick Union with Path Compression

I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function). I understand why it is $O ( ...
3
votes
3answers
87 views

Why are loops faster than recursion?

In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But ...
-1
votes
1answer
36 views

Give a function that is in EXPTIME but is not in O(2^n) [on hold]

Give a function that is in EXPTIME but is not in O(2^n). Thanks.
-1
votes
1answer
33 views

How fast can one compute the power of a number?

Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \{0\}$ then how fast can one compute $x^k$? If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many ...
3
votes
1answer
21 views

Algorithm for grouping identical neighbors in a list

I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries. Example list: ...
0
votes
2answers
81 views

What is the time complexity of this algorithm?

In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed: She represented the cost of the algorithm by the following sum: ...
3
votes
1answer
17 views

Is there an alternative to full factorization for testing the Polya conjecture?

The Polya conjecture is a disproved conjecture that states over half the numbers less than any number has an odd number of prime factors. It first fails at $n = 906,150,257$, thus being a good example ...
1
vote
0answers
18 views

Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also ...
1
vote
1answer
38 views

How often can a linear speed sort succeed?

Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$. What kind of bounds can we place ...
3
votes
1answer
30 views

Replacing n with 2n in asymptotic bounds

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem $6$ of the paper on page 632, the authors go on ...
0
votes
3answers
120 views

Find a weighted median for unsorted array in linear time

For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of weighted median in linear time. It is very simple to do ...
18
votes
2answers
302 views

How to find the element of the Digit Sum sequence efficiently?

Just out of interest I tried to solve a problem from "Recent" category of Project Euler ( Digit Sum sequence ). But I am unable to think of a way to solve the problem efficiently. The problem is as ...
-1
votes
2answers
83 views

Time and space complexity of removing duplicates in a sorted list

Is it possible to delete duplicates from a sorted array in $O(\log N)$ time and $O(1)$ space?
3
votes
1answer
57 views

Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)

Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$. Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but ...
0
votes
0answers
40 views

Find keys between $x$ and $y$ in binary search tree

Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the ...
3
votes
3answers
43 views

Complexity of finding factors of a number

I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division: For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ ...
0
votes
1answer
41 views

PSPACE and DTIME $2^{cn}$

This is a HW question that I'm stuck on and was hoping for some help. we're supposed to prove that: PSPACE not equals DTIME($2^{cn}$) for every $c>0$ (or actually for the union of all $c>0$) ...
6
votes
1answer
120 views

Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) ...
0
votes
3answers
79 views

Size of instance after reduction

A decision problem $C$ is $NP$-complete if $C$ is in $NP$, and every problem in $NP$ is reducible to $C$ in polynomial time. Reduction means transforming an instance of one problem $A$ to an instance ...
5
votes
1answer
98 views

Implication of Berman and Hartmanis conjecture

I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture : All $NP$-Complete languages are $p$-isomorphic. Then the book says that ...
1
vote
2answers
38 views

How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index?

The standard way a search engine retrieves documents is by using an inverse index from words in the query to document ids. Since the ids are sorted, a query like "word1 AND word2" would fetch the ...
1
vote
1answer
44 views

If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ...
1
vote
2answers
62 views

Is it true that P is not equal to deterministic linear space complexity class?

I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class? Is there some proof? Or should I find some algorithm which is not ...
-1
votes
0answers
14 views

How do we know that xTIME is a subset of xSPACE?

I'm just starting with Complexity and I can't figure out why do we say that xTIME is a subset of xSPACE (for x in ...
1
vote
0answers
28 views

(Why) is there no complexity class for linear space (O(n))? [duplicate]

tldr: I'm looking for any general information about the linear space complexity class. e.g. is there a complete problem for it? the Quantified Boolean Formula (QBF) problem is a P-space complete ...
-1
votes
1answer
48 views

Problem in computational complexity (superior class)

Say that a class $C_1$ is superior to a class $C_2$ if there is a machine $M_1$ in class $C_1$ such that for every machine $M_2$ in class $C_2$ and every large enough $n$, there is an input of size ...
1
vote
1answer
40 views

Why is ZPP = RP ∩ co-RP?

I am trying to prove the theorem that ZPP = RP $\; \cap \; co-RP$. If $L \in \; \subseteq RP \; \cap \; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, ...
0
votes
1answer
41 views

How to compute Jacobi symbol efficiently?

How do I compute the Jacobi symbol $(N|A)$ efficiently? In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod_i Q_{p_i}(A)$ where $p_1, \dots , p_k$ are all the (not ...
7
votes
3answers
475 views

The difference between theoretical complexity and practical efficiency

If I have this pseudocode: for i=0 to n/2 do for j=0 to n/2 do ... do anything .... The number of iterations is $n^2/4$. What is the complexity of ...
4
votes
1answer
64 views

Sorting array with at most two inversions

I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case. I have no idea how to prove that it is optimal in terms of the ...
4
votes
1answer
31 views

Combine $k$ sorted lists into one

Say I have $k$ sorted lists of the same size $n/k$, and I want to combine them into one sorted array in $O(n\log k)$ time. The solution I came up with is to recursively halve the lists until you ...
0
votes
0answers
52 views

Complexity of active set method for Quadratic Programming

The Quadratic Programming problem is as follows: $$\min_x \{\frac12x^THx+x^Tg\}$$ $$Ax\le b$$ where $H$ is symmetric and positive semi-definite. What is the complexity of the active set method for ...
4
votes
1answer
73 views

See that P$^{NP}_{||} = P^{NP}_{O(\log n)}$

I'm trying to prove that P$^{NP}_{||} =$ P$^{NP}_{O(\log n)}$ where $n$ is the length of the input. So, to see that polynomially many non-adaptive queries to a problem in NP can do as much as ...
1
vote
1answer
42 views

Prove that the depth function of a Binary Search Tree is $O(\log n)$ on average

I am struggling with this question because I am not sure how to see that a depth function is $\mathcal{O}(\log n)$ on average when it clearly traverses through the whole tree which should make it ...
1
vote
1answer
56 views

What is the worst case time complexity for intersection tests with BVHs?

This question is in the context of computer graphics. We have a scene with $n$ triangles and a ray. We want to find if the ray intersects any triangle and get the closest one. There is a ...
2
votes
1answer
24 views

On graph isomorphism over exponential word sizes

Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes? (Shamir's poly time Integer Factoring algorithm is over exponential word sizes).
1
vote
2answers
61 views

Big-O and little-o notation

I think I have a passable understanding of what Big-O and little-o mean. I'm just wondering whether it makes sense notation-wise to state something like the following: $$O(n^c) = o(n^k) \text{ for } ...
3
votes
1answer
50 views

Examples of languages not decidable by a TM using certain upper bounds on space/time

I'm learning about time and space complexity involving Turing Machines at the moment, and would really like some concrete examples of specific languages that belong (or don't belong) to certain ...
1
vote
2answers
62 views

Time complexity of comparing two $N \times N$ Matrices?

So each matrix has $N^{2}$ elements, and so just by comparing each element we would be doing $O(N^{2})$ operations. Is there any other way to compare these two matrices such that the number of ...
3
votes
1answer
43 views

Linear equation solving with special sparse coefficient matrix

Given a linear equation system of $n$ equations with unknowns $a_1,a_2,...,a_n\in [0,1]$, where the left hand side of each equation consists of not more than $k$ variables (so there are at least $n-k$ ...
1
vote
1answer
22 views

What is the correct way to define time constructible functions?

Sipser defines a time constructible function as $f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $f(n)$ in binary to the output tape in ...
1
vote
2answers
52 views

Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$

Given an array $a$, I want to count all triplets of indices $x,y,z$ such that $a[x] > a[y] + a[z]$. I can think of two solutions: Go over all triplets of indices $x,y,z$ directly. This takes ...
0
votes
0answers
6 views

How can I arrive at an asymptotically tight upper bound and prove its correctness? [duplicate]

I am aware of Big-Oh, but often times my bounds are sloppy, which while correct is not tight enough. How can I ensure that my bound is tight? Is there a way to prove or mathematically arrive at an ...
0
votes
0answers
21 views

How to calculate order of growth for the given loop? [duplicate]

int sum = 0; for (int i = 0; i < N; i++) for (int j = 1; j <= N*N; j = j*2) sum++; According to me the outer for loop will run O(N), and the ...
3
votes
2answers
104 views

Identifying system events affecting timing behavior of an application

Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job? My question is purely in the context of Worst Case ...
1
vote
1answer
38 views

About showing algorithmic gap instance for the Goemans-Williamson SDP

Using usual notation we have, $SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$ where we mean, $SDP(G)$ = The maximum value that the SDP finds of the objective ...
-1
votes
1answer
34 views

Is the complement of the given language necessarily in NP?

$A$ is a given language so that $A \in NP$. Assume that $P = NP$. Is $A'$ necessarily in NP? What I did: $A \in NP , P=NP$ $P=coP$ (Can be proven by running a TM $M$ as a decider for ...
1
vote
2answers
86 views

Proving that the language of satifiable CNF formulae with primes is NP-complete

Given the following language: $$L=\left\{\langle\phi, n\rangle \ \middle|\ \begin{array}{l}\phi\text{ is a satisfiable Boolean formula}\\ \text{written as POS (in CNF form)}\\ \text{and $n$ ...
4
votes
0answers
57 views

Upper bound complexity for a tree's particular property

I want to determine if in a given binary tree whose nodes are integers, left subtree's (let's call it L) nodes are multiples of (at least one) right subtree's (R) node(s). I only require ...
5
votes
1answer
71 views

Finding a small element in a changing array

Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like. The array is initialized to zeros. The goal to to support two operations: ...