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
4
votes
1answer
61 views

Maximize area of light with 4 light sources on a diagram of a room

Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized. Here is a simple ...
2
votes
3answers
46 views

Determining the number of iterations needed to find the number of bits in an integer

I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer. ...
1
vote
1answer
40 views

Using Subset Sum algorithm $O(n)$ times to find the subset

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
0
votes
1answer
264 views

Is time complexity of the greedy set cover algorithm cubic?

I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements....
1
vote
1answer
56 views

What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
0
votes
1answer
23 views

Making an algorithm that picks a unique random number in fixed set more efficient

I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have ...
1
vote
1answer
21 views

Lowest complexity - Number closest to 0

I'm currently trying to improve my algorithm skills and I was trying a simple algorithm : Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his ...
0
votes
1answer
31 views

Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$

I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold. $T(n)= 5T(n/4) + n^2$ Guess: $T(n) = O(n^2)$ Prove: $T(n) \leq cn^2 $ ...
1
vote
2answers
133 views
0
votes
3answers
93 views

Sum rule for Big-O with equal complexity-functions?

One property of the Big-O-notation is the sum rule, which states that when I have two functions $f_1$ and $f_2$ and their corresponding complexity functions are $g_1$ and $g_2$, then the combined ...
1
vote
2answers
388 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
1
vote
1answer
35 views

Big-O of iterating through nested structure

While trying to understand complexity I run into an example of going through records organized in following way: ...
0
votes
2answers
61 views

Does DFS have better constants/complexity than Backtracking on a Graph?

I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
5
votes
4answers
1k views

Is it possible for the runtime and input size in an algorithm to be inversely related?

I'm wondering if it's possible for algorithms that have monotonically decreasing runtime with the input-size - just as a fun mental exercise. If not, is it possible to disprove this claim? I haven't ...
0
votes
1answer
64 views

Is this computational complexity of the k-NN (custom distance) correct?

I read on a book that in general k-NN (no optimizations), given $d$ dimensions $n$ examples every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
3
votes
1answer
179 views

“Fuzzy” Chinese Remainder Theorem

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&\equiv a_3 \mod 7 \...
0
votes
1answer
31 views

Determine if there is a subset of the given set with sum divisible by a given integer

I've been given a question to solve: Given a set of non-negative distinct integers, and a value $m$, determine if there is a subset of the given set with sum divisible by $m$. For this question the ...
3
votes
1answer
85 views

Maximal subsets of a point set which fit in a unit disk

Suppose that there are a set $P$ of $n$ points on the plane, and let $P_1, \dots, P_k$ be distinct subsets of $P$ such that all points in $P_i$ fits inside one unit disk for all $i$, $1\le i\le k$. ...
1
vote
3answers
234 views

What complexity does this 'how many ways to climb' algorithm have?

I have a solution to the following problem: Given a stairway of $n$ stairs, which you can climb from $1$ to $m$ at the time ($1 \leq m \leq n$), return all the ways you can climb the stairway. ...
0
votes
1answer
93 views

Estimating run time of of while loops?

i, sq ← 1, 1 while sq < n for j ← 1 to sq k ← 1 while k ≤ j k ← 2 ∗ k i ← i + 1 sq ← i ∗ i I have Expressed the running ...
2
votes
2answers
88 views

Efficient way to reduce a binomial coefficient as a fraction

Here is the full problem. You need to calculate Euler's totient function of a binomial coefficient $C_n^k$. Input The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$. ...
1
vote
3answers
111 views

Can you insert into sorted list with time O(1)?

Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap ...
3
votes
1answer
86 views

Disprove unrealistic speed-up of total Turing machines

Let $T_1$ be a total Turing machine deciding language $L_1$, and let $I_1$ and $I_2$ be two separate inputs to $T_1$. Further, let $I_{c}$ be $I_2$ concatenated to $I_1$ with some separation symbol in ...
3
votes
3answers
92 views

Are there any examples of projects running a program that will take many years to finish its job?

There are algorithms that are said to be unfeasible to be applied in practice due to their time complexity. In textbooks, it's common to see remarks like "it would take hundreds of years" ...
1
vote
1answer
224 views

CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...
0
votes
1answer
26 views

Given two identical DOM trees find same node in tree B

So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'. I can solve it in two ways - Start at the given element and traverse up to ...
2
votes
2answers
41 views

Algorithmic problem with many different time/space complexity solutions

I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or ...
3
votes
1answer
244 views

efficient algorithm for min cut with specified number of vertices

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
0
votes
1answer
397 views

Modular exponentiation running time

I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student). Is it poly ...
3
votes
3answers
150 views

What is the complexity of $i^i$?

What is the complexity of the following algorithm in Big O: for(int i = 2; i < n; i = i^i) { ...do somthing } I'm not sure if there is a valid operator to ...
-1
votes
0answers
33 views

NP-class of set partitioning problem with equal number of elements in each partition

The question is : State and explain if the following problem is NP problem: In a set of positive integers, determining if the set can be split in half where halves have equal sum. this problem can be ...
0
votes
1answer
49 views

Bubble Sort: Runtime complexity analysis line by line

I'm trying to analyze Bubble Sort runtime in a method similar to how to it's done in "Introduction to Algorithms 3rd Ed" (Cormen, Leiserson, Rivest, Stein) for Insertion Sort (shown below). ...
0
votes
0answers
28 views

Time complexity about Maximum subarray

I recently came across a function called the strawman algorithm which the pseudo code looks like this: ...
2
votes
2answers
57 views

Description logics with decision problems within NP

Is there any description logic where important decision problems (e.g. abox consistency or concept satisfiability) lie within NP with respect to their time complexity? The well-researched family of $\...
0
votes
1answer
26 views

what would be the time complexity of DBSCAN algorithm?

what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?
0
votes
1answer
43 views

Analysis of Pan-cake sorting

i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort). However it is mentioned that the A[i] has to be a ...
1
vote
1answer
36 views

Difficulty understanding the use of arbitrary function for the worst case running time of an algorithm

In CLRS the author said "Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$, since for a given $n$, the actual running time varies, depending on the particular ...
2
votes
2answers
86 views

How does f(n) < cg(n) specify time?

I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes: $O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n_0$ ...
1
vote
1answer
50 views

While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?

While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity ...
0
votes
0answers
29 views

Selecting n elements from array in sublinear time and subquadratic compute and memory complexity using indices

Are GPUs or CPUs capable of selecting n elements from an array in sublinear time using indices? If so, what would be some good alternatives to achieve this? Lets say I have an array A = {1, 5, 6, 3, 6,...
3
votes
1answer
114 views

Survival algorithm for Network deterministic failures

Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
-1
votes
1answer
55 views

What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case

Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
-1
votes
1answer
36 views

How to know if time complexity is O(n+m) or O(n*m)

I'm having difficulty understanding when can we know if the time complexity of an algorithm is n+m or n*m Is the time complexity of the following algo O(n+m) or O(n*m) Can you please point me to a ...
1
vote
1answer
545 views

Finding all unique paths from a source to a sink in a specially-formed DAG

Let $G$ be a directed, acyclic graph of order $n$, such that: $G$ has exactly one source vertex $s$; $G$ has exactly two sink vertices $t_1, t_2$; The out-degree of any non-sink vertex in $G$ is ...
0
votes
1answer
301 views

Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
0
votes
1answer
32 views

Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array ...
0
votes
2answers
71 views

Big O notation, code time complexity

does appending an element to a list through a for loop work in O(1) time or O(n) time? In addition, what is the time complexity does "".join that list into a string work in?
1
vote
2answers
74 views

Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could ...
1
vote
1answer
121 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
0
votes
1answer
54 views

Upper bound for runtime complexity of LOOP programs

Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions. Furthermore primitve recursive functions can (as far as I ...

1
2 3 4 5
36