FAQ Database Discussion Community

## How can we prove that the running time bound of an algorithm is tight?

algorithm,big-o,computer-science,big-theta
Suppose we can prove that an algorithm, invoked with an input of size n, runs in time O(f(n)). I want to prove that this running time bound is tight. Two questions: Wouldn't it suffice to give a special input and show that the running time is at least f(n)? I've...

## Intro to Algorithms (chapter 1-1)

algorithm,big-o
Just reading this book for fun, this isn't homework. However I am already confused on the first main assignment: 1-1 Comparison of running times For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t,...

java,math,big-o
This question is related to another stackoverflow discussion distance between long&lat points Here is the code from the top voted answer: /* * Calculate distance between two points in latitude and longitude taking * into account height difference. If you are not interested in height * difference pass 0.0. Uses...

## Big O notation for g(n) > h(n)

algorithm,big-o
I've got this function: f(n) = g(n) + h(n) g(n) > h(n) Is this result always correct for Big O notation? O(g(n)) Thank you....

## I'm timing a function that has a runtime of O(n^3) but my timing results do not show this, why is this happening?

matlab,big-o,time-complexity
numberOfTrials = 10; numberOfSizes = 6; sizesArray = zeros(numberOfSizes, 1); randomMAveragesArray = zeros(numberOfSizes, 1); for i=1:numberOfSizes N = 2^i; %x=rand(N,1); randomMTimesArray = zeros(numberOfTrials, 1); for j=1:numberOfTrials tic; for k=1:N^3 x = .323452345e-999 * .98989898989889e-953; end randomMTimesArray(j) = toc; end sizesArray(i) = N; end randomMPolyfit = polyfit(log10(sizesArray), log10(randomMAveragesArray), 1); randomMSlope =...

## Big O notation for the complexity function of the fourth root of n

algorithm,math,big-o,time-complexity,complexity-theory
I am expected to find the Big O notation for the following complexity function: f(n) = n^(1/4). I have come up with a few possible answers. The more accurate answer would seem to be O(n^1/4). However, since it contains a root, it isn't a polynomial, and I've never seen this...

## Understanding Big-Ω (Big-Omega) notation

algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

## Ternary vs Chained If-else-if (Performance)

c#,performance,if-statement,big-o,ternary
I did the due-diligence to see if this has been asked before and didn't find anything identical but close, so here goes. Say I have a chain of if-else-if statements. foreach (value in valueList) if (value == 120) { w = true; } else if (value == 140) { x...

## Which Algorithm is faster?

algorithm,big-o,code-complexity
Our Lecturer gave us his code procedure linear_search (x: integer; a1, a2, …, an: integers) i := 1 while ( i ≤ n and x ≠ ai ) i := i + 1 if i ≤ n then location := i else location := 0 and this is mine method...

## How to find out time complexity of mergesort implementation?

algorithm,big-o,time-complexity
We all know that merge sorting algorithm time complexity is "N Log N". But from this below code how to calculate this "N Log N" big O notation step by step ? There are some answer about this question on internet but they are very complicated to understand. Please help...

## Where do exponent denominators (fractional exponents) in big-O time complexity come from?

algorithm,big-o,time-complexity
In algorithm descirptions, I sometimes encounter time complexities that look like: O(n29/20+m7/3). I see where + and numerators in powers come from: + means successive loops, and numerators mean nested loops. For example this (useless) algorithm has O(n2+m) time complexity: public int compute(int n, int m) { int answer =...

## Algorithm time complexity with binary search

time,big-o,time-complexity,binary-search-tree,binary-search
I am trying to figure out what the time complexity of my algorithm is, I have algorithm with binary search, which is in general O(log n), I know. But I search between two constants, namely x=1 and x = 2^31 - 1 (size of integer). I think that in the...

## How are the following functions O(N^3)?

algorithm,big-o
I'm taking the "Intro To Algorithms" course on Coursera, and I've arrived at the video which deals with Big-Theta, Big-Omega and Big-O notation. The end-of-video quiz presents the following question: Q: Which of the following functions is O(N^3)? a) 11N + 15lgN + 100 b) (N^2)/3 c) 25,000*(N^3) d) All...

## time complexity of non-inplace binary search

big-o,time-complexity,complexity-theory,binary-search
Assuming that binary search is called upon a subarray of approximately length n/2 and that there are at most three comparions at a level I came up with T(n) = T(n/2) + 3 as a recurrence relation. But: When I call binarySearch recursively isn't the cost of the slice proportional...

## Storing pairwise sums in linear space

arrays,algorithm,sorting,big-o,asymptotic-complexity
If we have two arrays of size n each and want to sort their sums, the naive approach would be to store their sums in O(n^2) space and sort it in O(n^2 logn) time. Suppose we're allowed to have the same running time of O(n^2 logn), how would we store...

## Big-O of Triple Nested Loop

java,big-o
What would the Time complexity (Big-O) of such an algorithm be for (int i = 1; i < n; i++) { for (int j = 1; j < i; j++) { for (int k = 1; k < j; k++) { x++; } } } Is it exponential? Assuming the...

## Big O with removing an element each time

big-o,asymptotic-complexity
Hi i am trying to find out the big-O of this algorithm. I think it is n^2 but because the size of the sub loop is shrinking each time I am not sure. for(int i= 0; i < SIZE; i++){ for(int j = i; j < SIZE; j++) { //Code...

## Update minimum spanning tree if edge is added

algorithm,graph,tree,runtime,big-o
I have a possible solution for the following question, but not sure if correct: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is...

## Big O of this short code

javascript,algorithm,big-o,time-complexity
I would need to determin the Big O of this short code: var iterations = 0; function operation(num){ iterations++; if (num == 0) return 1; return operation(Math.floor((num / 10) * 2)); } var result = operation(1000); alert('Result = ' + result + ', number of iterations = ' + iterations);...

## Big-O complexity java

java,big-o
I'm new to Java, my question is on big-O complexity. For a), it is clearly O(n^2) for a nested loop. for ( int i = 0; i < n; i++) for ( int j=0; j < n; j++ ) however, for b), with sum++ operation at the end, and complications...

## Big-O of Dijkstra's Algorithm with D-Ary Heap

algorithm,heap,big-o,dijkstra
I'm looking for a complete walkthrough on the runtime of Dijkstra's algorithm when implemented with a D-Ary heap. My best understanding as of now is that the depth of the tree is at most log_d(n), so the max time of insertion and bubbling up is log_d(n). Wouldn't bubble down be...

## Sum of all subparts of an array of integers

arrays,algorithm,sum,big-o,subset
Given an array {1,3,5,7}, its subparts are defined as {1357,135,137,157,357,13,15,17,35,37,57,1,3,5,7}. I have to find the sum of all these numbers in the new array. In this case sum comes out to be 2333. Please help me find a solution in O(n). My O(n^2) solution times out. link to the problem...

## Confused about the big O notation of the code

python,big-o
I was trying to find if the given strings are anagrams without using any helper sort function and nested loops. Therefore I tried using a while loop; however, I am not sure what the big O notation of this code is. Can you please help? def anagrams(string1, string2): if len(string1)...

## Compare growth of function

algorithm,big-o
I have the following: n! nlogn 2 ^ n sqrt3(n) = n^1/3 n ^ 3 We know that in order to compare two functions we need lim n->infinity f(n) / g(n) But we also know that exponential > polynomial > polylogarithmic. We also know from stirling that n! = o(n^n)...

## Determining the Big O complexity for “for” loops.

big-o,time-complexity
I have 3 for problems I having trouble determing the Big O complexity for. A. int x = 0; for ( int y = 1; y <= n * n; y++) for ( int z = 1; z < y; z++ ) x++; I want to say n3 because the...

## Ruby- delete a value from sorted (unique) array at O(log n) runtime

ruby,arrays,big-o
I have a sorted array (unique values, not duplicated). I know I can use Array#binarysearch but it's used to find values not delete them. Can I delete a value at O(log n) as well? How? Lets say I have this array: arr = [-3, 4, 7, 12, 15, 20] #very...

## Algorithm efficiency analyze

algorithm,big-o
I need some help with a task given in lecture today; Given algorithm of O(n∙log n). n = 2048 elements runs on a specific computer on 11 sec. How long time will the same algorithm use one the same computer with n = 8192 elements? Im not really sure how...

## Why are my nested for loops taking so long to compute?

algorithm,matlab,time,big-o,nested-loops
I have a code that generates all of the possible combinations of 4 integers between 0 and 36. This will be 37^4 numbers = 1874161. My code is written in MATLAB: i=0; for a = 0:36 for b= 0:36 for c = 0:36 for d = 0:36 i=i+1; combination(i,:) =...

## Why is only one of the given statements about complexity classes correct? [closed]

algorithm,big-o,time-complexity,complexity-theory
Apparently the correct answer to the following question is (C), but why are the other options not correct until we know the value of n? If n=1, all of these seem correct except (B)! Where am I going wrong? Which of the following is not O(n2)? (A) 1510 * n...

## O notation proof for exponents and power

algorithm,big-o,time-complexity,complexity-theory,exponential
I am trying to prove that 4^n is not in the order of O(2^n). Is this a valid method ? 4^n >= c*2^n => 4^n/2^n >= c => 2^n >= c I got lost here......

## Would this algorithm run in O(n)?

algorithm,big-o,time-complexity,complexity-theory,asymptotic-complexity
Note: This is problem 4.3 from Cracking the Coding Interview 5th Edition Problem:Given a sorted(increasing order) array, write an algorithm to create a binary search tree with minimal height Here is my algorithm, written in Java to do this problem public static IntTreeNode createBST(int[] array) { return createBST(array, 0, array.length-1);...

## BIG O In absence of enough information

performance,algorithm,big-o,complexity-theory,growth-rate
So, lets say you have a function, X(N) that is a total black box. You don't know the growth rate of the function, you can't look it up, and you can't view the source (at the moment). Next lets examine it in the context of another function for(int i =...

## Big-O proof involving a sum of logs

math,big-o,logarithm
Prove that I put the series into the summation, but I have no idea how to tackle this problem. Any help is appreciated...

## Update minimum spanning tree if edge is removed

algorithm,graph,tree,runtime,big-o
I am having trouble with the following question: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is removed from G to produce a...

## Solving recurrence equation without the Master's Theorem

big-o,recurrence-relation
So, on a previous exam, I was asked to solve the following recurrence equation without using the Master Theorem: T(n)= 9T(n/3) + n^2 Unfortunately, I couldn't figure it out on the exam, so I used solved it using the Master's Theorem just so I could know the answer (but, of...

## Big O complexity decision

java,algorithm,big-o
I got a big doubt regarding the complexity analysis of this code. I need to study the complexity of the "encontrarCaminos()" method and I'm torn between it being O(n*m) since it gets to iterate n times (thru an array.aslist (Caminos) finding all the simultaneous ways thru a maze -in which...

## Big O notation for brute force solution

big-o,asymptotic-complexity
I am working through programming problems from InterviewCake[1] and this problem[2] is confusing me. I have an array stock_prices_yesterday where: - The indices are the time, as a number of minutes past trade opening time, which was 9:30am local time. - The values are the price of Apple stock at...

## Is the execution time of this unique string function reduced from the naive O(n^2) approach?

c++,c,algorithm,big-o
The generic algorithm to deduce if a string contains all unique characters (and that does not use any other data structures) says to go through the string, iterating each letter against the entire string searching for a match. This approach is O(n^2). The approach below (written in C) uses an...

## Would this function be O(n^2log_2(n))?

big-o,computer-science
So I am given a function like 65536 n2 + 128 n log2n and the only way that this would be O(n2 log2n) is if C = 65664, n0 = 2 for all n ≥ 2 since C1 = 65536 n1 = 2 when 65536 ≤ C1*n2 and C2 =...

## what are the relationship between O(nlogn)+O(n), O(nlogn) and O(nlogn + n)?

algorithm,big-o
Intuitively, I thought the three expressions are equivalent. For example, if an algorithm runs in O(nlogn) + O(n) or O(nlogn + n)(I'm confused), can I say that's an O(nlogn) algorithm? what's the truth?...

## What is the big o notation of this algorithm?

big-o
for(int i = 0; i < n; ++i) { for(int x = i; x < n; ++x) { // work... } } What is the big o notation for this type of algorithm? Also, please explain to me how you came up with the solution. Also, sorry for the vague...

## Running time Functions for nested for-loop

performance,algorithm,big-o,analysis,growth-rate
for the following nested for-loops I am in trouble to compute running time functions. 1- for(int i = 1 ; i <= N ; i++) for(int j = 1 ; j * j <= N ; j *= 2); 2- for(int i = 2 ; i <= N ; i...

## What is the Time Complexity of finding the max k integers?

python,algorithm,dictionary,big-o,time-complexity
def max_k_sort(k, nums): # sort nums first using timsort # add O(n*log(n)) time complexity sorted_nums = sorted(nums) return sorted_nums[-1*k:len(nums)] def max_k(k, nums): # build initial max number list max_nums = {} # add O(k) time complexity? i = 0 while i < k: max_nums[i] = 0 i += 1 #...

## Counting the basic operations of a given program

c++,performance,runtime,big-o
I am looking at the following: Operations Counting Example Which is supposed to present the operations count of the following pseudocode: Algorithm prefixAverages(A) Input array A of n numbers Output array B of n numbers such that B[i] is the average of elements A[0], A[1], … , A[i] for i...

## Big O notation example confusion

big-o
The problem in this case is asking if 22n = O(2n)? Now usually I solve for both inequalities in 0 <= 22n <= c*2n. 0 <= 22n is trivially true, and then I rewrite the other inequality as: 2n*2n <= c*2n, and the 2n cancel out, leaving us with 2n...

## Big-O insert for 2 dimensional array

c++,c,arrays,big-o
If i have N x N 2 dimensional array and the name is a. int a[N][N]; When i Insert any value in any array, for example, a[N-1][N-1]=1, how much time does it take? O(N^2) or O(1)?...

## Most efficient way to calculate Fibonacci sequence in Javascript

javascript,algorithm,big-o,fibonacci
I'm attempting to get better with optimizing algorithms and understanding big-o, etc. I threw together the below function to calculate the n-th Fibonacci number. This works (for a reasonably high input). My question is, how can I improve this function? What are the drawbacks of calculating the Fibonacci sequence this...

## Partitioning a set of values in Python

python,algorithm,dictionary,data-structures,big-o
I wrote a function that tries to partition a list of values into contiguous chunks. A chunk is a set of values in which values from the start through to the end would be present in the list. As an example, consider the list [1,2,3,7,7,8,9]. This would be partitioned into...

## How is it possible for Java HashMap to perform constant time lookup O(1) for “get” operations?

java,algorithm,hashmap,big-o
I understand the basics of how a HashMap works - hm.put(obj) finds the correct bucket to place the object into, based on the obj.hashCode value. Then within that bucket if another object .equals(obj) then replace it, if not add it to the bucket. But I am unclear on how HashMap.put...

## TIme complexity of various nested for loops

loops,for-loop,big-o,time-complexity,asymptotic-complexity
Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount. loop 1 ---- for (int i = 1; i <=n; i *= c) { // some O(1) expressions } loop 2 ----- for (int i = n; i >...

## Big-O for 2 dimensional array and Linked list

I've made a game by using 9 linked Lists and the other 1 linked lists gets all the address of the other 9 linked lists. Therefore, something like a 2 dimensional array by using linked list. I'm trying to calculate Big-O that my data structure fits and is better than...

## What is the Big-O complexity of this code?

big-o,time-complexity
What would be the big O for void fun(int n) { for(i=1; i<=n; i=i+2) { } } My answer: O(log n) (since the i values is 1,3,5,7,9 reducing by 2 overall) void fun(int n) { for(i=1; i<=n; i=i+2) { } } My answer: O(log n), since this is quadratic (i...

## Complexity O(n^3) vs O((logn)^4))

big-o
I would like to prove that O(n^3) is bigger than O((logn)^4). I thought that I can divide both powers with 4 so it is O(n^0.75) vs O(logn) but then I don't know how i can prove that (n^k) is bigger than O(logn) for k>0....

## Best algorithm to find N unique random numbers in VERY large array

performance,algorithm,big-o,bigdata,asymptotic-complexity
I have an array with, for example, 1000000000000 of elements (integers). What is the best approach to pick, for example, only 3 random and unique elements from this array? Elements must be unique in whole array, not in list of N (3 in my example) elements. I read about Reservoir...

## How can i find a running time of a recurrence relation?

recursion,big-o,complexity-theory
The running time for this recurrence relation is O(nlogn). Since I am new to algorithm how would I show that mathematically? T(n) = 2⋅T(n/2) + O(n) T(n) = 2 ( 2⋅T(n/4) + O(n) ) + O(n) // since T(n/2) = 2⋅T(n/4) + O(n) So far I can see that if...

## Dropping non-constants in Algorithm Complexity

algorithm,graph,big-o,complexity-theory,bellman-ford
So, basically I'm implementing an algorithm to calculate distances from one source node to every other node in a weighted graph, and if a node is in a negative cycle, it detects and marks that node as such. My question regards the total time complexity of my algorithm. Assume V...

## Why do we ignore co-efficients in Big O notation?

algorithm,big-o,time-complexity,complexity-theory
While searching for an answer of Big O Notation I have googled a lot and have also seen many SO answers like link 1, link 2, link 3 and many more, but still I have not clearly understood some points. One of them is why do we ignore / remove...

## Performance Improvement Basics in Python

python,algorithm,performance,big-o
So this is an algorithms question I was working out on HackerRank. It passes all the test cases except one because it times out. I tried making a couple of improvements but it still keeps timing out. I want to understand how you can look at your own code and...

## Finding sum of x^k from k= 0 to n in O(logn) time

c,algorithm,big-o
So my question is how to do this in C more specifically. I'm aware that O(logn) usually means that we'll be using recursion by somehow splitting one of the parameters. What I'm trying to achieve is the sum of k = 0 to n of xn. for example exponent_sum(x, n)...

## Compute the “lower contour” of a set of segments in the plane in `O(n log n)`

c++,algorithm,big-o,computer-science
Suppose you've a set s of horizontal line segments in the plane described by a starting point p, an end point q and a y-value. We can assume that all values of p and qare pairwise distinct and no two segments overlap. I want to compute the "lower contour" of...

## Proof of O(loga n) = O(logb n), for any base a or b

algorithm,big-o,logarithm
I am revising for my exams and this question appears on a past paper: Show that O(loga n) = O(logb n) for any choice of logarithmic bases a and b working from the mathematical definition of the order notation f(n) E O(g(n)). Could someone please show me how to solve...

## Exponential growth doubling processor speed

algorithm,big-o,complexity-theory,exponential
According to Wikipedia article on Exponential growth E.g. if a slow processor can solve problems of size x in time t, then a processor twice as fast could only solve problems of size x+constant in the same time t. My question is, how do we calculate the constant value that...

## For sets S and T, why does Python's S -= T take O(len(T)) and not O(len(S))?

python,big-o,python-internals
The Set entries in this Python time complexity table say, and the comments below confirm, that S.difference_update(T) takes time O(len(T)) while S - T takes O(len(S)). The reason given is that the algorithm for the first is "for every element in T remove it from S", while the algorithm for...

## Why, algorithm and data structure, both are not considered together when doing Big O complexity analysis?

algorithm,data-structures,big-o,time-complexity
I have been reading about algorithms and data structures & their performance characteristics. I want to understand - How running time of a program is affected by the Big O complexity analysis of a particular algorithm against a particular data structure. For e.g. in a Red-Black Tree structure, searching in...

## How to find the Big O when there are two separate for loops

c,for-loop,big-o
I know how to find Big O for "for loops" and nested "for loops", but what happens when we have two for loops, not nested but two separate for loops in the same function.

## Determining the big-O runtimes of loop with inner loop repeat time is const

algorithm,math,big-o,time-complexity,complexity-theory
I have a function for(int i=0;i<n; i++) { b[i]=0; for(int j=0;j<5;j++) { b[i]=a[j+i] } } I need to calculate big-O of above function. My answers is: Inner loop run 5n time => O(n). So the total complexity is O(n). I think I have a mistake in my calculations, but I...

## time complexity analysis for finding the maximum element

algorithm,big-o,time-complexity,lower-bound
I've encountered a homework problem. which of these is an asymptotically tight upper bound for the best-case running time of an optimal algorithm that finds the maximum element in an arbitrary array of integers of size n (1) O(logn) (2) O(n^2) (3) O(n) (4) O(1) (5) O(nlog(n)) Based on my...

## Big O Nested for Loop issue

java,big-o
public static void main(String[] args) { int count = 0; int n = 20; for (int i = 0; i < n; i++) { for (int j = i; j > 0; j--) { count++; } } System.out.println(count); } Above is the code of a simple nested for loop...

## Binary search complexity for 10 elements is 0(log 10) = 1 , but the comparision required are 4

algorithm,search,data-structures,big-o,binary-search
The following set has 10 elements {10, 20, 21, 22, 23, 40, 50, 56, 90, 100} N = 10 O(log 10) = 1 if the element 20 has to searched then 4 compare operations has to be performed (i.e) 1-comparision 10 2-comparision 23 (since mid value of 10 elements) 3-comparision...

## Why is the cost of a hash lookup O(1) when evaluating the hash function might take more time than that?

hash,hashtable,big-o,time-complexity
A HashMap (or) HashTable is an example of keyed array. Here, the indices are user-defined keys rather than the usual index number. For example, arr["first"]=99 is an example of a hashmap where theb key is first and the value is 99. Since keys are used, a hashing function is required...

## Time complexity of python code for finding the longest word that can be made of other words in the list

python,performance,big-o,time-complexity
I am preparing for some coding interviews and came up with a solution to the following problem: "Find longest word that can be made of other words in a list of words". I have a hard time figuring out the time complexity of my algorithm. It would be great, if...

## is this the most efficient way?

java,arrays,big-o
I'm looking for the greatest difference between 2 doubles in a list, I have done it this way in NlogN time, is there a way to do it in linear time? thanks! public static double NlogN(double[] ar){ Arrays.sort(ar); double max=ar[ar.length-1]; double min=ar[0]; double difference=max-min; return difference; } ...

## How to calculate the T(N) for this primes finder algorithm

algorithm,big-o,complexity-theory
This algorithm find all prime numbers below N var f = function(n){ var primes = [2]; //1 var flag; //1 for(var i=3; i<n; i+=2){ // ( from 3 to n-1 ) / 2 flag = true; //1 var startI = 0; // 1 for(var y=primes[startI]; y<=Math.sqrt(i); y=primes[++startI]){ // ??? if(i%y...

## Calculating the Recurrence Relation T(n)=T(n / log n) + Θ(1)

algorithm,recursion,big-o,complexity-theory,recurrence
The question comes from Introduction to Algorithms 3rd Edition, P63, Problem 3-6, where it's introduced as Iterated functions. I rewrite it as follows: int T(int n){ for(int count = 0; n > 2 ; ++count) { n = n/log₂(n); } return count; } Then give as tight a bound as...

## Algorithm for matrix addition and multiplication

algorithm,matrix,time,big-o,matrix-multiplication
Let m, n be integers such that 0<= m,n< N. Define: Algorithm A: Computes m + n in time O(A(N)) Algorithm B: Computes m*n in time O(B(N)) Algorithm C: Computes m mod n in time O(C(N)) Using any combination of algorithms A, B and C describe an algorithm for N...

## Time complexity of Boggle solver

python,algorithm,big-o,time-complexity
Here is a (ugly) algorithm for finding all words in Boggle: d = {'cat', 'dog', 'bird'} grid = [ ['a', 'd', 'c', 'd'], ['o', 'c', 'a', 't'], ['a', 'g', 'c', 'd'], ['a', 'b', 'c', 'd'] ] found = {} N = 4 def solve(row, col, prefix): if prefix in d...

## Analysis of a Bubble-sort algorithm

algorithm,sorting,big-o,bubble-sort
Normally the running time complexity of a buublesort is O(n^2) but the algorithm given below has a while loop and a for loop the for loop depends upon n but the while loop is simply a checker for a boolean value. Can anyone tell me how would i calculate the...

## What is the complexity of function f(n) with n=f(n).log(f(n))

algorithm,math,big-o,complexity-theory,logarithm
What is the complexity of function f(n),preferably the Big-O notation, and f(n) satisfies the condition n = f(n).log(f(n)) ,f(n) > 1 .Let assume that log in base 2. I tried to isolate f(n) from the condition but could not get it done. After using excel to get the graph of...

## Which Sieve of Eratosthenes implementation is more efficient?

java,algorithm,big-o
I have two implementations of the Sieve of Eratosthenes. Here's the first: public class SieveOfEratosthenes extends PrimeGenerator { private boolean[] sieve; private List<Integer> primes; public SieveOfEratosthenes(int depth) { super(depth); sieve = new boolean[depth + 1]; primes = new ArrayList<>(); generate(); } private void setPrime(int n) { sieve[n] = true; primes.add(n);...

## Wouldn't this algorithm run in O(m log n)?

java,algorithm,runtime,big-o,time-complexity
I am working on an interview question from Glassdoor Software Engineer The question is     Given a list of one million numbers, how will you find the top n numbers from the list in an efficient way Here is a solution an author gave from same link create a...

## first and last terms of a nested loop, sums of arithmetic series starting with non zero index

algorithm,math,big-o,computer-science,integer-arithmetic
I have 2 arithmetic series... (i) for i<- 1 to n do for j<- 1 to 2n-i do //a unit cost operation So the first term is 2n-1, last term is 2n-n = n (ii) for i <- 1 to n do for j <- 2 to (n+i) do //...

## Big O of 2 separate comparisons vs. comparison with 2 expressions

algorithm,big-o
Are these two the same in big O notation? 1: If False do something If True do something 2: If False or True do something ...

## Interpreting multivariate big-Oh notation

algorithm,big-o
I'm dealing with a situation right now where I have an algorithm whose complexity is determined by three independent variables l, m, and n. One implementation of the algorithm runs in O((l + m)*log^2(l + m) + (m + n)*log^2(m + n)) time and another runs in O((l + m...

## Best and worst case time for Algorithm S when time complexity changes in accordance to n being even/odd

algorithm,big-o,asymptotic-complexity,growth-rate
The following is a homework assignment, so I would rather get hints or bits of information that would help me figure this out, and not complete answers. Consider S an algorithm solution to a problem that takes as input an array A of size n. After analysis, the following conclusion...

## Choose the right algorithm

c++,algorithm,big-o
I have this problem: there is a integer vector of N elements, I call it A. Then there are two elements, I call them (P,Q), such that 0<= P <= Q <N (P,Q are indexes of A). We use the two elements to compute L = A[P] + A[Q] +...

## Decreasing the run time for my recursive subset sum algorthim

java,algorithm,recursion,big-o,subset-sum
I have a recursive DFS algorithm that correctly counts the amount of subset sums there are. However, the run time for this method is absurd and extremely exponential. For example, when arr contains the set below. The sum we are looking for is 50. The arr has all duplicates and...

## Binary search - worst/avg case

search,big-o,time-complexity,complexity-theory,binary-search
I'm finding it difficult to understand why/how the worst and average case for searching for a key in an array/list using binary search is O(log(n)). log(1,000,000) is only 6. log(1,000,000,000) is only 9 - I get that, but I don't understand the explanation. If one did not test it, how...

## Can you do addition/multiplication with Big O notations?

algorithm,big-o,time-complexity
I'm currently taking an algorithm class, and we're covering Big O notations and such. Last time, we talked about how O (n^2 + 3n + 5) = O(n^2) And I was wondering, if the same rules apply to this: O(n^2) + O(3n) + O(5) = O(n^2) Also, do the following...

## What is the big-O complexity of this code

big-o,time-complexity
Whats the big-O notation of this code? for( int i=1; i<2n; i++) x=x+1; My answer = O(2*n) Is this correct?...

## How can I tell how many times these nested statements will execute?

algorithm,sorting,big-o,time-complexity,complexity-theory
I have the following pseudocode: SelectionSort(A) n = A.length for j=1 to n-1 smallest = j for i=(j+1) to n if A[i] < A[smallest] smallest = i exchange A[j] with A[smallest] I think that the first for-loop test will execute n times, and the nested for-loop will execute 1 +...

## Determining number of calls (activations) to mergesort

algorithm,big-o,mergesort
I'm studying for a CS 125 final exam, and Big O Notation was covered (briefly). Given that: Mergesort has a Running Time Best Case of O(N lg(N)) and Running Time Worst Case of O(N lg (N)) There are 32 floating point values, initially in random order, stored in a double...

## Have I properly sorted these runtimes in order of growth?

math,big-o,time-complexity,asymptotic-complexity
I am doing this small task which I have to arrange asymptotic runtime in ascending order. Here are the runtimes: Here is the order I believe they should go in: log10(n^4), n^3, 2^((log4n)), 2^(100n), e^pi^4096, n! + 12^1000 Is this correct? Or are there any errors? Thanks!...

## Big O Notation with Absolute Value?

graph,big-o,notation
I'm going through some programming interview question books, and I've seen reference to "O(|A|)" time complexity. I've never seen this notation with the absolute value given. Some research led me to Big O Cheatsheet that references this notation under the graphs section. The problem I'm researching is about partitioning an...

## What is better BigO log(m*n) or (m+n)?

algorithm,big-o
With m and n being the two dimensions of a 2D matrix, which search algorithms with givens Big-O are considered faster: log(m*n) or (m+n) or log(m)*log(n)? ...

## How to get Omega(n)

algorithm,big-o,complexity-theory,big-theta
I have the formula a(n) = n * a(n-1) +1 ; a(0) = 0 How can i get the Omega, Theta or O Notation from this without the Master Theorem or did anyone have a good site to understand the explanation...

## Big-O run time for adding N items into ArrayList

java,arraylist,big-o
Say I'm adding N items to an ArrayList in Java. What is the worst-case run time for this? I know it can be O(N) to add a single item because the array may have to resize. It won't resize N times as I add N items or even a factor...

## What is the complexity of these two string based algorithms?

java,performance,algorithm,big-o,time-complexity
I have written these two algorithms to check a string for duplicate characters (ABBC, AAAC). The first uses the hashset data structure, whilst the second relies purely on iteration. Algorithm 1 String s = "abcdefghijklmnopqrstuvwxxyz"; public boolean isUnique(String s) { Set<Character> charSet = new HashSet<Character>(); for(int i=0; i<s.length(); i++) {...

## Big-O Computational Resources

algorithm,sorting,big-o,computer-science,asymptotic-complexity
I know that measuring asymptotic complexity can be based on any resources you have, whether it's time, memory usage, number of comparisons, etc. But when it comes to sorting something, I realize we normally associate the asymptotic notation with the basic operations like number of swaps/steps or number of comparisons....

## algorithms: how do divide-and-conquer and time complexity O(nlogn) relate?

performance,algorithm,big-o,divide-and-conquer
In my Algorithms and Data Structures class a first divide-and-conquer algorithm namely merge sort was introduced. While implementing an algorithm for an assignment a few questions came to my mind. Does any algorithm that is implemented with the use of the divide and conquer paradigm has time complexity of O(nlogn)?...

## What part of my code is making my performance suffer? (Codility's MaxCounter)

java,algorithm,data-structures,big-o,time-complexity
I have the following problem: You are given N counters, initially set to 0, and you have two possible operations on them: increase(X) − counter X is increased by 1, max counter − all counters are set to the maximum value of any counter. A non-empty zero-indexed array A of...