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

2
votes
1answer
79 views

Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
2
votes
0answers
19 views

Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming

I have recently been working on an applied project where I have to solve optimization problems. I have found that it is much easier to solve an integer linear program (ILP) as opposed to a ...
2
votes
1answer
25 views

Top N percent elements in a Queue

I implemented a queue using two stacks which gives me O(1) enqueue time, O(1) amortised time. Now suppose i want to find top 10% elements in the Queue at any time. How am i suppose to implement it. ...
-4
votes
2answers
70 views

Sort doubly linked list efficiently

How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?
0
votes
0answers
26 views

Asymptotic Complexity of the following two functions [duplicate]

Let $f(n) = n^{1.01}$ $g(n) = n(log(n))^2$ Now I need to figure out whether $f = O(g(n))$ or $\Theta(g(n))$ or $\Omega(g(n))$. I tried taking the ratio $f(n)/g(n)$, apply L'Hospital's rule ...
0
votes
1answer
22 views

Understanding the time-complexity of Insertion Sort

From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below). The image above shows the times that each statement is executed. But wait, why is ...
1
vote
1answer
40 views

What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale?

Background: The pool ball weighing problem is a classic CS question thrown at students, typically to demonstrate a binary search (alternative to ripping phonebooks in half). Pool Ball Problem: Given ...
6
votes
0answers
80 views

Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine. Is ...
10
votes
1answer
108 views

Efficient algorithms for vertical visibility problem

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task: The problem: we are given a two-dimensional square box of side $n$ whose sides are ...
0
votes
0answers
20 views

Programming and evaluating sorting algorithms based on its complexity [duplicate]

I need to program and evaluate two sorting algorithms: insertion sort and merge sort I know that the complexity of insertion sort is O(n^2) and for the merge sort is O(n·log n) In this case I have a ...
4
votes
1answer
81 views

Complexity of Linear Diophantine equations

My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are ...
0
votes
1answer
37 views

tightest upper bound on binary search tree insertion? [closed]

The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that ...
0
votes
1answer
32 views

Inserting vertex in an adjacency matrix

If a graph with $v$ vertices is represented in the form of adjacency matrix . Then, adding a new vertex to the existing graph requires how much time ? Is it $O(v^2)$ or $O(2v)$ . We have the ...
4
votes
1answer
127 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
2
votes
0answers
31 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? The usual algorithms rely on indirect access, so how much does losing it cost us? Say we have $N$ integers from $[0, 2^B)$. It's not ...
7
votes
2answers
106 views

Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?

The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I ...
3
votes
2answers
76 views

Find rectangle of minimum area where dimensions are larger than minimum

Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = ...
7
votes
1answer
697 views

Why doesn't Knuth's linear-time multiplication algorithm “count”?

The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of ...
1
vote
1answer
38 views

What is the time complexity of the Bailey–Borwein–Plouffe formula?

How can I assess and derive the time complexity of the BBP formula? $$ BBP(n)=4S(1,n) - 2S(4,n) - S(5,n) - S(6,n) $$ where $$ S(j,n) = ...
3
votes
1answer
60 views

Computing the complement of a set

Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list. I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in ...
2
votes
1answer
69 views

Is FNP = FEXPTIME if and only if NP = EXPTIME?

It is very well known that if the classes $\sf FP$ and $\sf FNP$ are equal, then also the classes $\sf P$ and $\sf NP$ are equal (see e.g. FNP on Wikipedia). Is it also true that if $\sf ...
-3
votes
1answer
65 views

exponential lower bound on boolean formula conjunctions, what complexity class? [closed]

this new paper A Lower Bound for Boolean Satisfiability on Turing Machines by Hsieh asserts an exponential lower bound for a TM time complexity on a problem of finding whether a solution exists to a ...
6
votes
1answer
83 views

Computing the number of bits of a large power of integer

Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$? One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor ...
3
votes
3answers
82 views

Minimum number of tests to identify subset of modules that trigger a bug?

I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run. I can run the program with any desired ...
1
vote
2answers
97 views

Is the Calibron 12 puzzle NP-hard?

So, I was analyzing the Calibron 12 puzzle and to me it looks like a bin-packing problem. Is this puzzle actually a bin-packing problem and thus NP-hard for the perfect solution? Basically, you can ...
2
votes
0answers
39 views

Non-deterministic time hierarchy theorem: universal TM overhead

I am currently reading the book of Arora and Barak on computational complexity. In the third chapter (p69-70), two classic theorems regarding time complexity hierarchies are introduced: ...
2
votes
2answers
98 views

Why do Computers use Hex Number System at assembly language?

Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? ...
-1
votes
1answer
56 views

A difficult master theorem problem

Consider the function $B:\mathbb{N}\rightarrow\mathbb{R}$ defined by $$ B(n) = \begin{cases} 1 &\text{if $n\le 2$}\\ B\left(\left\lceil\frac{n}{\log_2n}\right\rceil ...
-1
votes
1answer
40 views

Is P^SAT subset of sum of NP and co-NP

I have a following problem: Let $P^{SAT}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle). Assume that: $co-NP \neq NP ...
1
vote
1answer
41 views

Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set

I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be ...
3
votes
1answer
50 views

Finding minimum path in a matrix algoritm

I'm looking for an algorithm that do the following thing. Given $n$ the number of rows and columns of a matrix of positive integers. Given $(x_1,y_1)$ the starting coordinates. Given $(x_2,y_2)$ ...
-3
votes
1answer
56 views

Compare runtime for algorithms?

I try to compute the asymptotic runtime for this algorithm and compare it with other algorithm $A = (C -(D * E ) ) mod p$ $ B = ((C * (D)^{-1} - (E * F ))$ mod p if we suppose each value A, B, C, D, ...
1
vote
1answer
85 views

Nested loops: Still $\mathcal O(n)$?

I have an algorithm similar to this: i=1 while(i < n) { //something in O(1) while(i < n && cond) { //something in O(1) i++ } i++ } ...
0
votes
1answer
72 views

Time complexity of Dynamic Array via repeated doubling

When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the ...
1
vote
1answer
103 views

Analysis of a recursive algorithm, where running time strongly depends on input

I want to find the worst-case running time of an algorithm, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where $T(x, i, y) = ...
0
votes
0answers
72 views

Recurrence Equation in Algorithm [duplicate]

Can anyone help me in solving this complex recurrence? \begin{eqnarray} T(n) &=& n +\sum_{k-1}^n T(n-k)+T(k) & Where& T(1) = 1. \end{eqnarray} although this topic will already ...
0
votes
0answers
23 views

Using arithmetic progression sum to show an algorithm is both $\Theta(n^2)$ and $O(n^2)$ [duplicate]

Exercise 4 in http://discrete.gr/complexity/ askes to give an arithmetic progression sum to show that the following algorithm is both $O(n^2)$ and $\Theta(n^2)$. ...
2
votes
1answer
85 views

Sorting numbers in $O(1)$

Here is an experiment I came up with (I don't have sufficient material to make it): Say that, you have a list of $n$ numbers $L = \{l_1, l_2, ..., l_n\}$. And you have bars representing those numbers ...
-1
votes
1answer
98 views

CNF H is in the class P

CNF H = {<ø>|ø is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal} I want to show that CNF H ...
3
votes
1answer
59 views

big O of a complex function

I have a complex function, which looks something like this: $$f(x) = \sum_{k=0}^x{\frac{g(k)}{h(k)}} + l(x)$$ Now, $g(k) = O(\log k)$ and $h(k) = O(k)$, the sum iterates $k$ from $0$ to the ...
2
votes
1answer
35 views

Understanding Expected Running Time of Randomized Algorithms

I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random ...
0
votes
0answers
18 views

TFNP and #P relation

Is there any known relationship between the complexity classes TFNP and #P. On first sight, it seems we can not compare them. Is there any work done either about this question, or about something ...
0
votes
0answers
26 views

The time complexity to find the largest rising left-neighbourhood for every element in an sequence? [duplicate]

For example, in sequence 3, 4, 3, 2, 4, the largest rising left-neighbourhood for 2 is 4 3 2 ...
1
vote
0answers
27 views

General object recognition versus specific object recognition

I have a question about the difference between general object detectors and specific object detectors. By specific object detectors, I'm referring to classifiers/object recognizers that are built to ...
1
vote
0answers
22 views

Grover algorithm for known number of solutions

I am reading Computational Complexity book and specifically Grovers search algorithm. I am aware that if we knew in advance exact number of solutions $K$, then the basic algorithm can be tweaked to ...
4
votes
1answer
132 views

Complexity of bitwise AND operation on bit string regular expressions

Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time ...
4
votes
1answer
73 views

Relation between RAM and Turing machine

Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers ...
3
votes
1answer
60 views

Complexity of factoring products of distinct prime numbers

Problem: Input is an integer number $x$ that we know factors as $p_{i_1}\cdot p_{i_2}\ldots p_{i_n}$, where the $p_{i_j}$'s are distinct prime numbers. Output is the above factorization of $x$. Do ...
1
vote
1answer
101 views

Inclusion of complexity classes (Deterministic Turing Machine)

I can't understand what my professor wrote about these inclusions concerning deterministic classes: $$ DTIME(f) \subseteq DSPACE(f) \subseteq \sum_{c\in\Bbb N}DTIME(2^{c(log+f)}) $$ I understood ...
4
votes
1answer
64 views

$NP\subseteq TIME[O(n^{\log n})]$

Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.