39 questions linked to/from What is O(...) and how do I calculate it?
8k views

Is O(log n) + O(log n) = O(n)? [duplicate]

We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity? For example, if I have a method to ...
9k views

What is O(m+n) and O(m*n) in Big O notation? [duplicate]

I understand that O(n) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. An example of this is a for loop: for n in 0.100 puts ...
2k views

What is Big O of sqrt(1) + sqrt(2) + … + sqrt(n)? [duplicate]

Given for example this code: for(int i=1;i<n;i++) for(int j=1; j < sqrt(i); j++) foo(); //foo takes constant time can someone explain to me how to calculate the ...
3k views

How does big O notation indicate upper bound on a function? [duplicate]

Suppose we have a function, f(n)=n+10. We say that f(n)∈O(n), meaning O(n) represents the upper bound of the function. It is also true that f(n)∈O(n2) or f(n)∈O(n3) and so on. So how can we say that ...
1k views

What exactly is “big O” notation? [duplicate]

From what I've gathered, big O notation is used to describe the length of an operation. However, that's as far as I've gotten. What exactly is big O notation and how do the most common ones (O(n), O(...
334 views

Big O of loop of 0…n with nested loop doing k iterations [duplicate]

My coworkers and I are discussing this code and need a third party to settle our discussion :) Random randNum = new Random(); int[] A = Enumerable.Repeat(0, 1000).Select(i => randNum.Next(0, 100))....
478 views

Big O notation for a sub linear algorithm [duplicate]

I have a function for which the complexity raise by the square ten of the exponent of the number. Ex: +-----+----------+ |Input|Complexity| +-----+----------+ |0 | 1 | |10 | 2 | |...
322 views

Does algorithm time complexity O(5) considered as O(1)? [duplicate]

I have someone homework to make and in the instructions it says that we need to implement a function in O(1). Now, does it mean that I can make my function in O(5) or O(2) or whatever?
112 views

time complexity for 3 foor loops different leangth [duplicate]

I have this method arr // input new_ seq = [] for i in arr: new_seq.append(i) __new_seq = [x for i, x in enumerate(arr) if x not in new_seq] for j in __new_seq: new_seq.append(j) ...
97 views

Help with Big-O notation complexity [duplicate]

How do I find the O - notation complexity for the following? int sum = 0; for (int i = 1; i <= n*2; i++ ) sum++; I read the guide on Big - O and other posts on Big -O complexity, but I'm ...
95 views

What does time complexity of n log n signify? [duplicate]

Is it the number of iterations or recursive calls made? Or is it the number of times the conditional check has been applied? Ex: if there are 10 elements in an array in descending order. The time ...
86 views

complexity of an algorithm, sorting 5% out [duplicate]

I have been asked the following question.. An algorithm considers n elements, sorts 5% of n out, considers the remain elements(95%), sorts 5% of the remain elements, and so on until finally one last ...
55 views

Questions around calculation of time complexity of an algorithm [duplicate]

I am a newbie to algorithms. One thing that i always get confused is about calculation of algorithm runtimes. For example: The following piece of code in Python for i in range(n): #O(?) i*=k ...