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
-1
votes
0
answers
69
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,784
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
295
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
1
vote
4
answers
262
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 ...
- 21
-4
votes
1
answer
112
views
What is the big O of this algorithm? [duplicate]
I think it's O(m*n) but someone said it's O(n). If you think it's O(n) could you provide an explanation?
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return ...
- 103
0
votes
3
answers
642
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
818
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
180
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
316
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 ...
- 771
2
votes
1
answer
535
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
250
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
378
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
2k
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,593
50
votes
8
answers
10k
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
2
votes
1
answer
266
views
Big-O Notation and Calculus [closed]
I was wondering if there are any calculus relationships implicit in Big-O notation.
For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
- 129
-3
votes
1
answer
162
views
What is the O of this operation?
Say for a given positive integer number n, you have to find a level k so that
1 + 2 + 3 + ... + k = S is below or equals n
but S + k + 1 is above n.
For example in python:
def find_level(n):
...
0
votes
1
answer
630
views
Is the complexity of this code quasilinear time?
Algorithm explanation: based on an unsorted list I want to find the indexes of the values in another sorted list. Note that all values are unique and the two lists have the same values, only in ...
- 103
4
votes
1
answer
266
views
How should I document a method's computational complexity in the code?
I am currently working on a project that has very little documentation overall. The team is working to change that. I am doing my part, by adding xml comments to the methods I make and the ones I edit,...
- 151
1
vote
3
answers
222
views
Big O Complexity when iterating in 3 dimensions
What time complexity would you classify the following as having?
int n = 100;
for(int x = 0; x < n; x++)
for(int y = 0; y < n; y++)
for(int z = 0; z < n; z++)
DoWork(...
- 2,128
-3
votes
1
answer
148
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
...
- 95
3
votes
3
answers
214
views
What is the complexity of find and checking prime numbers?
I'm trying to figure out the complexities of these two functions that I've written but could not understand.def
First, I thought it is supposed be O(N). But it is not clear how many times the loop ...
- 139
2
votes
2
answers
452
views
Generating O(N^2) without loops [closed]
I understand you can generate an O(N^2) algorithm by using loops:
eg:
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
//do something N^2 times.
}
}
Is it ...
- 309
0
votes
1
answer
705
views
Is my reasoning to determine this algorithm's Big-O correct?
Take the following algorithm with two separate sections, and the sections do not influence each other whatsoever (the function is not recursive, as well).
void algorithm(int x)
{
// This section ...
0
votes
2
answers
1k
views
What is meant with finding real and integer constants in Big Oh notation?
From my book "Data Structures & Algorithms in Java: Sixth Edition" the definition of Big Oh is the following:
Let f(n) and g(n) be functions mapping positive integers to
positive real numbers....
- 232
2
votes
1
answer
448
views
Am I allowed to simplify terms while calculating Big O?
I want to calculate the runtime of the following function
T(n) = (1+2+3+4+5+...+n)/n
At first this doesnt seemed hard to me because it can be solved easily by transforming the formula
T(n) = (n(n-1)...
- 131
19
votes
6
answers
5k
views
What do you call it when you change the Big O execution time of a function [closed]
Let's say I have a function which sorts a database in O(n^2) time. I want to go about refactoring it so it runs in O(n log(n)) time, and in doing so I will change the fundamental way the operation ...
- 723
0
votes
3
answers
170
views
Big-O when worst case numerical value is known
If I have an algorithm and part of it has a known worst case numerical value, which is reasonably small compared to the rest of the problem, is it ok to argue that part as O(1)?
E.g. If part of the ...
- 345
3
votes
3
answers
1k
views
randomly filling in empty spaces in a matrix - O(N) amortized time?
Here are two ways to answer the following question. I'm trying to confirm what I believe their time complexity to be:
If I had a snake game with a x,y matrix of spaces, some of which were occupied ...
- 182
-3
votes
1
answer
2k
views
What's the needed math for building algorithms? [closed]
What's the needed math for building algorithms? Because I was reading a book and I can't understand much. It says I need simple math from high school.
I don't want to learn all the math that exist ...
- 57
5
votes
2
answers
5k
views
Can "sub-linear" still be a straight line?
I'm working on a problem that requires a "sub-linear" solution.
A quick search for sub-linear will return a lot of this...
... where the sub-linear line is modelled as logarithmic/asymptotic.
But I ...
- 259
-4
votes
1
answer
97
views
Calculating Complexity
I am having trouble calculating the complexity of this problem:
REVERSE3(A): // Reverse the order of elements in an array
// P is an array; assume generating next permutation takes 1 step.
for ...
- 103
2
votes
6
answers
593
views
Does the workload problem belong to a class of computer science problem?
I went for an interview, and got a workload problem:
Problem: write a function to tell whether a series of workloads will exceed
the maximum workload or not
Input: MaxWorkLoad: example 10
...
- 1,827
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 ...
- 119
2
votes
1
answer
105
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 ...
- 129
-1
votes
2
answers
114
views
What programming environments can be used to illustrate and benchmark the unoptimized space complexity of an algorithm?
What programming language along with implementation and compiler can I use to study the pure, unoptimized space complexity of an arbitrary algorithm? And what methods can I use to do so?
For example,...
- 545
-1
votes
1
answer
2k
views
Big-Oh notation of a stackarray
I am studying data structures and I have hit a bit of a road block. The top is Big oh notation and it is simply confusing. While I can find the upper bound for the simplest of loops, when it comes to ...
- 19
1
vote
1
answer
120
views
omega why K + N better than N
I was reviewing the big O cheatsheet at http://bigocheatsheet.com/ and ran into some listings under sort that I do not understand.
Runtimes are color coded, green being better than yellow. There are ...
- 121
-1
votes
3
answers
502
views
Time complexity of an algorithm [closed]
What is the complexity of the following loop?
for(i=1;i<n;i=2^i)
sum+=i;
- 11
1
vote
1
answer
529
views
Big-O notation and halting problems
I'm trying to understand why it's impossible to create a tool that calculates Big-O notation automatically.
I have read about Halting problems, but not related on Big-O notation and I was wondering, ...
- 1,491
-1
votes
1
answer
60
views
Time complexity Computation
What will be the result of the time complexity of this piece of code i.e.
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++) {
sum = sum + A[i];
}
...
- 11
4
votes
5
answers
519
views
Efficient way to calculate how many items to destroy if each has a 70% chance to be destroyed
We start with a variable that holds an integer for the "number of items" that we have somewhere, somehow.
Then, the algorithm is applied: each one of those items have a 70% chance to be destroyed.
...
- 151
1
vote
1
answer
660
views
Should I use this very short Python Quicksort implementation?
def quicksort(N):
if len(N) < 2:
return N
else:
less = quicksort([number for number in N[1:] if number < N[0]])
more = quicksort([number for number in N[1:] if ...
user232181
4
votes
3
answers
19k
views
Finding longest subsequence with sum less than or equal to a fixed number
I was trying to solve Problem 279-B.
Given an natural number, t, and an array, a[0],...,a[n-1], of natural numbers, find the maximum length of a continuous subarray, a[i],...,a[j] in a where a[i]+.....
- 267
1
vote
2
answers
216
views
Understanding θ(f(n)) as defined in the Structure and Interpretation of Computer Programs
I'm having trouble understanding a small passage in The Structure and Interpretation of Computer Programs, and I'm hoping someone can help me interpret it.
In the book's introduction to Orders of ...
- 477
2
votes
2
answers
1k
views
O(n^2 * 2^(log n)) == O(n^2)
Is O(n^2 * 2^(log n)) == O(n^2) ?
Why I think that this could be the case:
In big O, you only take the parts of the term that are most relevant, right? O(n^2 + 3n + 9) == O(n^2). The n^2 has a lot ...
- 171
1
vote
1
answer
635
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?
- 21
1
vote
2
answers
2k
views
Binary Search O(log(n)) or O(n)
I see where most readings online derive that the Big-Oh notation of a Binary Search is O(log(n)), but doesn't this assume a balanced tree? What if the tree is completely unbalanced (i.e. similar to a ...
- 29
0
votes
1
answer
501
views
How to calculate big O notation according to number width?
I'm trying to understand big O with the bitwise operations. I have 2 functions those are solving the same question from different perspective.
num1BitsSecondSolution starts to shift the number right ...
- 469
2
votes
2
answers
6k
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 ...
- 157