Tagged Questions

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
1answer
20 views

Implement opposite() method to tell if there are two opposite numbers, (x,-x)

Let a dictionary with the operations insert(), delete() and search(). Each one of them ...
0
votes
1answer
43 views

Time Complexity of Queue Problem

What is the time complexity of the following problem? Definitions Given a discrete time axis, define a FIFO as a queue unit with the commands: PUSH (data to back of queue), POP (the head of the ...
2
votes
1answer
21 views

Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar ...
9
votes
1answer
262 views

Is there an efficient algorithm for expression equivalence?

e.g. $xy+x+y=x+y(x+1)$ ? The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or ...
2
votes
1answer
66 views

Are there any coP problems

Is there a notion of coP problem? Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?
0
votes
1answer
33 views

Time complexity for two multiplications modulo $p$

The time complexity of computing $MK\bmod P$ is $O((\log n)^2)$. What is the time complexity of computing $MK^2\bmod P$? Is it $O(2(\log n)^2)$ or $O((\log n)^2)$?
3
votes
3answers
134 views

Shouldn't complexity theory consider the time taken for different operations?

I have read the answer found here which considers the size of integers when doing comparisons and how that affects on the basic cost of comparison. I am trying to understand why each basic operation ...
2
votes
1answer
61 views

Average time to solve maze through backtracking

Given a set A consisting of all possible solvable mazes on an n by n square grid, what is the average running time to solve the mazes in A using a standard backtrack algorithm with no optimizations? ...
1
vote
2answers
33 views

What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

I am aware that as the number increases in Digits the process of locating the two prime numbers that when multiplied produce the given number is increased as well. I also know that is it somewhat ...
2
votes
1answer
53 views

What is the lower bound for finding the third largest in a set of $n$ elements?

The problem is easy to describe: What is the lower bound for finding the third largest in a set of $n$ elements? Particularly, do we have to know both the largest and the second largest for ...
1
vote
1answer
20 views

Big-O Notation for Menezes-Vanstone Elliptic Curve Cryptography?

I need someone help me about . how can compute time complexity for this algorithm (Menezes-Vanstone Elliptic Curve Cryptography). I have spent much time reading journals and papers but as yet have ...
2
votes
1answer
49 views

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3) I was told it takes: $$2(n-2) + 1 = 2n-3$$ However, I can't seem to figure out ...
1
vote
1answer
29 views

Sorting with a recursive oracle

It is known that the runtime complexity of sorting is $\Theta (n \log n)$. But what if we have, for every input array of size $n$, an oracle that can sort any array of $k<n$ numbers in constant ...
0
votes
1answer
43 views

Master Theorem Questions?

NOTE: I asked this on mathstackexchange, but didn't get the responses I wanted, thought I should post in CS. Sorry if i did something wrong but i am a newbie. State the asymptotic (worstcase) ...
0
votes
1answer
58 views

Proving that the average case complexity of binary search is O(log n)

I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations. But how would I go ...
2
votes
1answer
26 views

Runtime complexity of unary languages

I am trying to find a unary language whose runtime complexity is exponential in $n$ (e.g. $\Theta(2^n)$ or a similar expression). But I am not sure how to reason about the runtime of such languages. ...
2
votes
1answer
71 views

How can you iterate through a hash table in constant time?

I am studying data structures and the book "How to Think About Algorithms" by Jeff Edmonds (pages 46-47) claim that: "Hopefully, all the elements that are in your set happen to be placed into ...
0
votes
1answer
38 views

Creating all possible subsets and complexity calculation [duplicate]

I am a novice programmer and very weak in complexity calculation. I have learnt to write a program for creating all possible subsets from a set of elements, i.e. knapsack algorithm. Now I would like ...
1
vote
1answer
51 views

Order of a pseudo code

I am trying to find order of an bellow algorithm but I have no idea about, the problem like below we have an array of $n$ element name $T[1...N]$ and we have that $0\leq T[i] \leq i$ and $T[i] \in ...
1
vote
1answer
63 views

Prerequisites of computational complexity theory

what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical ...
0
votes
1answer
78 views

Time Complexity for matrix multiplication? [duplicate]

How can I find out the time complexity for the brute-force implementation of matrix multiplication for: Two square matrices ($n \times n$), Two rectangular matrices ($m \times n$) and ($n \times ...
4
votes
4answers
470 views

How can an algorithm have exponential space complexity but polynomial time complexity?

For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback ...
3
votes
0answers
61 views

Problems that provably require quadratic time

I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$. The problem needs to have the following properties: $\Omega(n^2)$ runtime proof for any algorithm - ...
0
votes
1answer
30 views

Understanding when to count key comparisons

I understand that for something like Linear search, this would be the key comparison: if(itemToFind == a[i]) return i; If I put this method into another ...
0
votes
1answer
29 views

Comparing Big O Complexity [duplicate]

I'm trying to compare two functions, such as f(n)=n^n and g(n)=n^10^10. I'm unsure if f(n) is O(g(n)) or vise-vera where g(n) is O(f(n)). From my understanding, n^n can be worse than n! and although ...
2
votes
1answer
92 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
25 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
64 views

Top N percent elements in a queue

I implemented a queue using two stacks which gives me $O(1)$ en-queue 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 ...
-4
votes
2answers
95 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
29 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
29 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
83 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
137 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
21 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
97 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
78 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
50 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 ...
3
votes
1answer
133 views

How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?

I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1). (a) Describe an algorithm that sorts an input ...
4
votes
1answer
130 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
52 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
116 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
78 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
740 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
42 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
62 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
70 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
69 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 ...
9
votes
1answer
118 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
87 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 ...