Questions tagged [big-o]
The Big-O notation is used to represent asymptotic upper bounds. It describes relevant time or space complexity of algorithms. Big-O analysis provides a coarse and simplified estimate of a problem difficulty.
137 questions
-2 votes
1 answer
144 views
Time complexity of an HAMT
A Hashed Array Mapped Trie has a time complexity of log32(n). According to the paper referred by this implementation, the 32 comes from the cardinality of the alphabet, which in this case is a 32 bits ...
- 163
0 votes
0 answers
100 views
What is the Big O notation of modifying an existing element in a heap data structure?
Wikipedia says "increase key" is O(log n) for a binary heap, but it is referring to an internal function. I'm not asking about that: Imagine the data structure had an external/public ...
- 6,844
2 votes
7 answers
4k views
Why is big O notation an asymptotic notation/analysis?
An asymptote in mathematics represents a value (line) to which the observed function constantly approaches. In other words, as the value of X increases towards infinity, i.e. decreases towards minus ...
- 147
3 votes
1 answer
320 views
Algorithms: How do I sum O(n) and O(mlog(n)) together?
I'm doing a running time analysis using the aggregate method and I'm a bit confused about what would be the result in this case. I have some intuition in inferring that it would be O(mlog(n)) but I'm ...
- 51
2 votes
4 answers
517 views
How do we define a "step" when calculating big O notation in an algorithm?
I'm learning about Big O notation and how it relates to computer science and I understand the sentiment behind Big O, however I'm struggling at understanding how we define a "step". In the ...
- 31
0 votes
3 answers
792 views
Why isn't a counter used to avoid nested for loops for index based operations?
Let's assume we have a method that we want to run as fast as possible and it needs to loop on a 2D array, naturally we would do a nested for loop as such: int[][] arr = new int[3][3]; for(int ...
- 51
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)?
- 27
0 votes
2 answers
1k views
Calculating time complexity of a code snippet
I am trying to calculate the time complexity of the below code snippet def func() { for(i=1; i<=n; i++) { for(j=1; j<=n; j=j+i) { print("hello") } }...
- 111
0 votes
2 answers
199 views
Big O notation of a program that takes 10x time for 3n input
I have a program that calculates N digits of Pi. I have measured that it takes 10x time to calculate 3n numbers, compared with the time for calculating n numbers. The source code also gives an ...
- 127
3 votes
1 answer
437 views
Why the names Omega and Theta in Big Omega and Big Theta?
There was a question asking what the "O" stands for in "Big O", the answer to which seems to be "Ordnung von"/"order of". I wonder what's the origin of the ...
- 791
2 votes
1 answer
595 views
Running time for simple for loops - Big O notation
I am currently doing some exercises with algorithms and I find myself in a huge problem. It seems that everybody understands this type of problem but I have a really hard time figuring it out. For ...
- 39
-2 votes
2 answers
302 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 <...
- 107
-4 votes
1 answer
429 views
What is the worst case Time Complexity for only the Divide Portion of the Merge Sort Algorithm?
Please, consider the below merge sort algorithm. Here we start with a divide portion which splits the array into halves and we do recursive operation on each half separately. I have ignored the merge ...
- 1
3 votes
3 answers
3k views
Are there any programs or IDEs that calculate Big-O notation on functions? Is this something that is possible to program into an IDE?
Is there anything that can calculate the Big-O notation of a function? While learning about Big-O, it is implied that it is pretty trivial to do in your head once you know the basic rules, however if ...
- 3,649
50 votes
8 answers
11k views
Why is the worst case for this function O(n^2)?
I'm trying to teach myself how to calculate BigO notation for an arbitrary function. I found this function in a textbook. The book asserts that the function is O(n2). It gives an explanation as to why ...
- 636