Questions tagged [time-complexity]
The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and lower order terms.
0
votes
0answers
16 views
Perfomance SQL Server 2017 Graph vs Neo4j
I am researching about graph databases. I stumbled into SQL Server 2017 and learned that they added the option to use a graph database. But I have some uncertainties about the performance. I watched ...
-1
votes
2answers
52 views
Is there is a difference in time and space complexicity between equalization sign and initialisation?
For example i have the following code:
int value = 10;
int firstMethod = value;
int secondMethod (value);
What is the difference in time and space if I use second method? Is it gonna take longer? Is ...
0
votes
4answers
53 views
How do I reduce complexity of my swap algorithm to sort 5 numbers?
I am practicing to manually sort 5 numbers by comparing them with each other I have to loop it with n^2 times but I want to reduce it.
a1 = 100
a2 = 90
a3 = 45
a4 = 8
a5 = 0
i = 0
while i < 25:
...
0
votes
1answer
36 views
Array Subset problem [least space with O(n) time complexity]
I want to write a function in java which takes 2 arrays as inputs & return true if smaller array is a subset of larger array
Is there a way to make this below code succint & more space ...
0
votes
0answers
16 views
Is there a way to scan an one-dimension array for an SVD so you can have complexity of O(n)?
I am trying to scan an one-dimensional array for Singular Value Decomposition(SVD) and the worst time and space complexity to be O(n) without using any secondary data structure.
They only way I ...
1
vote
1answer
16 views
Efficient method for finding index of first occurrence of a number in batched data other than for loop
I am doing a task in which i have data in form of frames stored in batches. Dimension of a batch is like (batch_size,400), i want to find index of first occurrence of number 1 in each 400 length frame....
1
vote
1answer
52 views
search palindrome number in a list of array. if there exist palindrome number in the list, return its size
Check if there exists a Palindrome Number in the list.
If found return its size, else return -1.
public class Program{
public static boolean palindrome(String list){
String reversedString ...
-2
votes
2answers
38 views
Modify binary search to find all integers in an array bigger than x and less than 2x with a time- complexity better than O(n)
Let A be a sorted array containing n distinct positive integers. Let x be a positive integer such that both x and 2x are not in A.
Describe an efficient algorithm to find the number of integers in A ...
0
votes
1answer
41 views
Create a queue linked list in linear time
I came up with this way of creating a linked list in C:
void queue(Node ** head, Node * object)
{
Node * tmp = (Node *)malloc(sizeof(Node));
*tmp = *object;
Node *last = get_Last((*head));...
-1
votes
1answer
26 views
R - equivalent function to 'length' with O(log(n)) complexity [duplicate]
I need to write an equivalent function to the function length -without using
length, of course. also it must be using a loop.
I need to write two versions for this function. the first, with O(n) ...
2
votes
1answer
83 views
Can Someone please explain me the logic of calculating big-O in my example
It is said the complexity of selection sort is O(N^2) but i don't get the logic since i'm reducing the number of times the loop executed. I understand for Code block 2 but not for code block 1
public ...
1
vote
1answer
25 views
Time complexity of the for-loop
I need to calculate the time complexity of the following loop:
for (i = 1; i < n; i++)
{
statements;
}
Assuming n = 10,
Is i < n; control statement going to run for n time and i++; ...
0
votes
0answers
35 views
What is the time-complexity for the “in” function in Python for STRINGS?
I am trying to find out what would be the time complexity if I m trying to look for a string B in A in Python?
I understand its different for Lists/Dictionaries etc. I also know its O(n) for lists. so ...
-1
votes
1answer
18 views
Running time of inclusion-exclusion principle
I should use inclusion-exclusion principle
to find the probability of intersection of a sequence of dependent events. I wanted to know that is there a polynomial time algorithm which can compute the ...
-4
votes
0answers
28 views
anyone have an idea about Time complexity for crime mapping algorithm
anyone have an idea about Time complexity for crime mapping algorithm. algorithm with crime mapping. i want to find the complexity or Big O of crime mapping algorithm. if any one can help me it would ...
1
vote
1answer
21 views
Find the running time of an algorithm
I was watching a youtube video on Time Complexity Analysis of Iterative Programs: https://www.youtube.com/watch?v=FEnwM-iDb2g
And I cannot figure out how he calculated what's happening to line 5.
...
-2
votes
0answers
26 views
Whats the space and time complexity of these functions? [duplicate]
I am a bit unsure of whether I am evaluating out the right Order of Growths in this question:
a) What is the time complexity of bar? What about foo?
b) What is the space complexity of bar? What ...
0
votes
1answer
28 views
QuickSelect average time complexity O(n) [HOW?]
I was learning QuickSelect to find Kth Smallest Number.
I understood the program.
But I am stuck with how the average time complexity of QuickSelect is O(n).
I have tried the code in Java and it ...
0
votes
2answers
29 views
Deletion complexity of last element in double linked list
If you want to delete Node A then you have to traverse only one and complexity will O(1)
If you want to delete Node C then you have to traverse two times and complexity will O(n)
If you want to ...
0
votes
0answers
40 views
What impact does 'Print' have in a program? [duplicate]
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
a=[]
count=0
while 1:
print n
c=n%10
...
1
vote
1answer
34 views
Subset sum (dynamic programming) in Python - complexity problem
I have a problem with some implementation of a function that solves the problem of a subset sum in Python.
We have dynamic programming here, so the complexity should be polynomial.
The problem is ...
0
votes
1answer
41 views
what's the time complexity of dependent nested loop?
could you tell me what's the time complexity of the loop,It seems to be O(n^2),but i don't know why.
int k=0;
for(int i = n / 2; i <= n; i++){
for(j = 0; j <= i; j++){
k++;
}
}
...
-4
votes
1answer
16 views
if f(n) = 2n^2 and g(n) = 1.01^n. Is f(n) = O(g(n))? Is f(n) = Ω(g(n))?
Let f(n) = 2n^2 and g(n) = 1.01^n. Is f(n) = O(g(n))? Is f(n) = Ω(g(n))? Justify your answers with a proof.
0
votes
0answers
13 views
If Redis Sorted Set is implemented with Skip List, why ZPOPMIN time complexity is O(log n)?
I already read this question and it isn't what I'm looking for.
AFAIK deleting first m elements in Skip List containing n elements takes O(m) or we can say O(1) if m is not significant. But why ...
1
vote
2answers
36 views
Time complexity of divide and conquer relation
I was trying two calculate the time complexity of below function.
I tried two different methods
1) Since nearly every time there will be two recursive calls .
we can write the recurrence ...
7
votes
2answers
99 views
Clustering while trying to minimise spare capacity
I am trying to cluster ~30 million points (x and y co-ordinates) into clusters - the addition that makes it challenging is I am trying to minimise the spare capacity of each cluster while also ...
0
votes
1answer
18 views
Double Ended Singly Linked List - Time complexity of searching
I have read that the time complexity of a searching for an element, which is located at end of the double ended singly linked list is o(N).
But since time complexity of searching for an element at ...
5
votes
1answer
60 views
How to determine Big-o complexity if it only depends on values of input rather than input size?
I just saw javascript code about sorting which uses setTimeout as shown
var list = [2, 5, 10, 4, 8, 32];
var result = [];
list.forEach( n => setTimeout(() => result.push(n), n));
It is ...
2
votes
1answer
32 views
Comparison of time complexity
I got those two algorithms with two for loops each - the first algorithm has in my opinion a quadratic running time. Does the second algorithm have the same running time - O(n^2)?
Algorithm 1:
for (...
0
votes
0answers
28 views
Efficient algorithm for pairwise nearest neighbor search
Suppose that I have a dataset in R^(n * d) of n data points each with d dimensions. I would like to compute the k nearest neighbors of each of these n points amongst themselves, resulting in an N^(n*...
0
votes
0answers
34 views
Binary tree - lists of combination of nodes
I have got a binary tree with "length" (value) of every edge. I want to gather all possible sums of these edges ≤ k. Let's use an example.
The rules are simple. I have to gather all of combinations ...
0
votes
2answers
46 views
How will summing a sub array affect time complexity in a nested for loop?
Trying to calculate time complexity of some simple code but I do not know how to calculate time complexity while summing a sub array. The code is as follows:
for i=1 to n {
for j = i+1 to n {
...
0
votes
0answers
61 views
Finding individual sums of all possible tree after removing edges
Given a tree with N nodes with non-zero weights of nodes, how many trees (removing one or more edge) of this tree will have sum of weights as x (given)?
For example :
N = 3, weight of each vertex ...
0
votes
2answers
79 views
3sum algorithm complexity
This code finds if in a sorted array there are three numbers that add up to a given sum, but I'm not sure how to calculate its time complexity. Would love your input and ideas on how to improve it as ...
0
votes
2answers
24 views
Time complexity of operations on a sorted array of sorted lists
I have a sorted array of N elements equally distributed in K lists that is also sorted. What will be the time complexity (in tightest Big-O notation) for:
Removing the smallest element.
Resorting ...
-5
votes
1answer
45 views
Python code example for 'square root' time complexity [closed]
I'm learning about the different Big O time complexities, and the last one I have is the 'square root', but I just can't seem to find any useful Python code snippets that uses a simple algorithm for ...
0
votes
0answers
30 views
time complexity with hackerRank using java
public class Solution
{
public static void main(String[] args)
{
Scanner sc= new Scanner(System.in);
int p=sc.nextInt();
int ld[]=new int [p];
for(int i=0;i<p;i++)
ld[i]=sc....
0
votes
4answers
116 views
How can I reduce the time complexity of the following block of code?
I am taking 1 to n digits and finding count of numbers that are divisible by a or b but not divisible by both.
I want to reduce time complexity of this block by some logical change.
cin >> n &...
3
votes
4answers
124 views
Writing a function for F(n)=0.5F(n-1)
let F(n)=0.5F(n-1) and F(0)=1
a. write a function fun1, a recursive function to evaluate the n's term
b. write a function fun2, a non recursive function to evaluate the n's term
c. what ...
0
votes
1answer
57 views
Time complexity of inserting `n` elements in a `java.util.PriorityQueue` with `initialCapacity=n`
I have to construct a max-heap out of an array (called nums in the following code) and so I'm using java.util.PriorityQueue.
My code looks like this:
PriorityQueue<Integer> pq = new ...
0
votes
1answer
26 views
Using Timeit within a while loop and increasing input size
I'm stumped. Basically, I have two functions that take an input (which is a list of randomly generated numbers).
Then I wanted to figure out the size of the input list in which the time it takes both ...
0
votes
1answer
39 views
What would be time complexity for loop running till 2 to power n
What would be time complexity for loop running till 2 to power n?
Refer to below code snippet.
int[] arr={1,2,3,4};
for(int i=0;i<arr.length;i++){
for(int j=0;j<Math.pow(2,i);j++){
...
0
votes
1answer
25 views
Calculate Time Complexity In This Function
Given this function (written in pseudocode) what's the time complexity? Trying it out i would say the time complexity is θ(n^3) since we need to traverse the tree first θ(n) then multiply the ...
1
vote
1answer
42 views
Artificial Intelligence: Time Complexity of IDA* Search
I am studying informed search algorithms, and for Iterative Deepening A* Search, I know that the space complexity is O(d), where d is the depth of the shallowest goal node. I have tried to find out ...
0
votes
2answers
34 views
how to reduce time complexity for getting the factor of long type
i have to find the factor of some particular number and store it in an arraylist and at last i have to retrieve one number based on the index value from that arralist.
i am getting correct result for ...
0
votes
1answer
49 views
Error with verilog generate loop : Unable to bind wire/reg/memory
I am building a signed multiplier verilog code based on Row Adder Tree (binary tree) architecture and modified baugh-wooley algorithm.
However, I am facing issue with generate loop as follows when I ...
1
vote
1answer
49 views
Frechet distance in O(n)
I have seen on a number of articles that the Fréchet algorithm complexity is O(n^2).
That the paths represent as an Q and P arrays, of n size each
What if I start from Q[0], P[0] and check all the ...
-1
votes
0answers
22 views
How we can represent worst case or best case running time in terms of asymptotic notations? [closed]
When we can represent worst-case running time of an algorithm in terms of big-oh notation and when we can represent worst-case running time of an algorithm in terms of theta notation. For example ...
0
votes
0answers
43 views
Find the start city of the journey
I recently had an interview where I asked if I was given a set of trips that formed a journey, what will be the starting point of the whole journey?
For example, I provide a set of few trips ...
1
vote
1answer
22 views
What is the number of maximum comparisons intersection algorithm can perform?
So I have this algorithm below which finds common elements in two SORTED arrays. Given that both arrays have m and n lengths respectively, I need to find the maximum amount of comparisons this ...