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
0
votes
0answers
6 views

Is it true that $f(n) = c*g(n) + O(g(n))$ implies $f(n) = O(g(n))$?

Is this true for all $n$ and some $c>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows: $f(n) = c*g(n)$ for all $n$ and some $c>0$ is the definition of Big-Oh. So, $...
1
vote
0answers
24 views

A genral Turing model with one tape to define sublinear space (L,NL,..)

A genral Turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
-1
votes
0answers
10 views

Big-$\mathcal{O}$ Complexity of Converting a Base 10 Integer to Base $b$ [duplicate]

Let $N$ be a positive integer. (1) I would like to convert $N$ to base-$2$ (2) I would like to convert $N$ to base-$b$, where $b$ is an arbitrary base. Question: How may I accomplish this in a ...
2
votes
3answers
57 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. ...
0
votes
1answer
25 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
22 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
2answers
37 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
135 views

Time complexity of pairs in array double loop

I know, that the following is: O(n^2), ...
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: ...
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
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 ...
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 ...
3
votes
1answer
87 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 ...
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 ...
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" ...
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 ...
-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 ...
3
votes
3answers
151 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 ...
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: ...
0
votes
1answer
27 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})$?
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
30 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,...
0
votes
1answer
51 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). ...
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
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 ...
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 ...
1
vote
2answers
45 views

What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity ...
0
votes
0answers
11 views

What does increasing the input size by a factor of 100 do to a linearthimic algorithm with the complexity of 2nlog(n)

So far what I've tried to do is break this into parts and work from there So for the $2n$, increasing by a factor of 100 means the runtime goes up by 100 times But I get stuck with the log(n) part. ...
0
votes
3answers
94 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
0answers
38 views

Complexity of find histogram bins vs convex hull

For a list of n 2d points, finding the convex hull vertex takes O(n log(n)) time. And O(n) time if it’s sorted lexicon order. Meanwhile What’s the complexity of finding the histogram bin edges of k ...
1
vote
0answers
44 views

Complexity Values for Specific Code/Functions

(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
0
votes
0answers
34 views

Reconstructing an Array via Time-Intensive Subset Queries

I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem. I am given access to an ...
2
votes
0answers
37 views

How do you convert an NP problem which runs in O(f(x)) time in a SAT instance with O(f(x)*log(f(x))) variables in O(f(x)*log(f(x)))

I looked at the Cook's theorem at Wikipedia which presents a way to convert any NP problem to SAT but it seems to require O(f(x)^3) variables. Is it possible to remove some of the checks in the ...
1
vote
1answer
24 views

Relations between deciding languages and computing functions in advice machines

I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current ...
0
votes
1answer
44 views

algorithm to find shortest path connecting EVERY node

I have received a problem to solve and I am not sure what algorithm to use. TLDR; Find the shortest path to get to every node in a undirected graph The problem states that one must visit every ...
0
votes
1answer
61 views

How do you calculate the running time using Big-O notatation?

I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod(): ...
0
votes
0answers
25 views

Calculating the running time of Quicksort's PARTITION procedure

I am confused about calculating the PARTITION procedure's running time. PARTITION procedure is used in the Quicksort Algorithm to partition the array $A[p...r]$ I analyzed the PARTITION procedure ...
0
votes
0answers
25 views

$NP$ is not in $P(n^k)$ for any fixed $k \geq 1$

I encountered this problem which asks to show that for any fixed $k \geq 1$, $NP$ is not contained in $P(n^k)$... As an attempt, I thought of using the time hierarchy theorem which says that there ...
-1
votes
1answer
29 views

If $j − 1 < \log k < j$. Why is $j = O(\log k)$?

If $j \in Z^+$ and $k \in R^+$ and $j − 1 < \log k < j$. Why is $j = O(\log k)$? (All log's are in base 2) I know I have to find constants where $j <= c \cdot \log k$ but I need some help ...
0
votes
2answers
77 views

Time complexity of printing prime numbers within a range?

I've written an answer to this question, which asks about the following: What is the time complexity for the given code that prints prime numbers from start to <...
0
votes
1answer
39 views

How do I calculate the time complexity of this memoized algorithm?

The problem is: count all increasing subsequence of s. ...
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
72 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
0answers
24 views

Finding Smallest Frontier for Graphs of bounded pathwidth

Let $G$ be a graph and $X=x_1,x_2,...,x_n$ be an permutation/ordering of the vertex set of $G$. We then let $S_i = \{x_j:j\le i\}$, and $F_i$ be the number vertices $v\in S_i$ that are adjacent to ...
0
votes
1answer
37 views

Worst Case for AVL Tree Balancing after Deletion

After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST). The Balancing ...
0
votes
1answer
21 views

Complexity of generating power sets

Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a ...
0
votes
1answer
42 views

how to reduce the time complexity?

I have a graph G=(V+E) and list of list Node where each sublist is subset of V. I want to ...

1
2 3 4 5
36