Linked Questions
52 questions linked to/from What is O(...) and how do I calculate it?
7
votes
3
answers
15k
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 ...
3
votes
3
answers
33k
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 ...
2
votes
2
answers
7k
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 ...
1
vote
2
answers
5k
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 ...
3
votes
1
answer
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(...
-2
votes
2
answers
286
views
Is looping an array to compare to itself considered O(n^2)? [duplicate]
Often when I'm doing an operation comparing an array to itself, I write code along these lines:
function operation (array) {
for (let i = 0; i < array.length; i++) {
for (let j = i + 1; j <...
-2
votes
1
answer
1k
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 |
|...
-1
votes
1
answer
648
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))....
1
vote
1
answer
688
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?
-1
votes
1
answer
135
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)
...
-3
votes
1
answer
219
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
...
2
votes
1
answer
109
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 ...
1
vote
0
answers
98
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 ...
0
votes
0
answers
96
views
O(nlogn) + O(logn) =? [duplicate]
So I came upon this time complexity result and I was confused about it, it said that :
O(nlogn) + O(logn) =O(log(n+1))
Why is that the case? Shouldn't the result be O(nlogn)?