A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

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.

Filter by
Sorted by
Tagged with
44
votes
7answers
8k 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 ...
2
votes
1answer
161 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 ...
-3
votes
1answer
156 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
1answer
174 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 ...
3
votes
1answer
153 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,...
1
vote
3answers
188 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(...
-3
votes
1answer
56 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
3answers
142 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 ...
2
votes
2answers
311 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 ...
0
votes
1answer
91 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
2answers
504 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....
2
votes
1answer
214 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)...
19
votes
6answers
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 ...
0
votes
3answers
155 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 ...
3
votes
3answers
504 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 ...
-3
votes
1answer
855 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 ...
5
votes
2answers
3k 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 ...
-4
votes
1answer
92 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 ...
2
votes
6answers
540 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
vote
0answers
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 ...
1
vote
1answer
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 ...
-1
votes
2answers
91 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,...
-1
votes
1answer
1k 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 ...
1
vote
1answer
111 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 ...
-1
votes
3answers
192 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;
1
vote
1answer
319 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
votes
1answer
56 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]; } ...
4
votes
5answers
501 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. ...
1
vote
1answer
596 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 ...
4
votes
3answers
9k 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]+.....
1
vote
2answers
128 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 ...
2
votes
2answers
888 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 ...
1
vote
1answer
326 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
vote
2answers
809 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 ...
0
votes
1answer
495 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 ...
2
votes
2answers
3k 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 ...
2
votes
4answers
2k views

What is Big-O notation for purely functional languages?

Is it still relevant? Instead of var result = new List<int>(); for (var i = 0; i < prev.Count; ++i) { result.Add(prev[i] * 2); } where the result.Add, prev[i], and * 2 instructions are ...
-6
votes
1answer
743 views

BST to AVL in O(n) [closed]

I found in different places on the internet how to turn a Binary Search Tree into an AVL tree in O(nlog(n)). I was wondering how can this be done in O(n) (as the worst case limit). It kinda seems ...
1
vote
1answer
181 views

Complexity of recursive calls

my brain is a little stuck as I am trying to compile an example for my blog. I am presenting an algorithm that draws a number from an array, adds it to a sum and calls itself recursively. func solve(...
1
vote
1answer
66 views

Expressing complexity based on length of key

I've made a data structure that has insert, search, and delete functions that are base on the number of characters in the key. As an example if it's a number based key (base10), then the complexity ...
4
votes
1answer
630 views

How does cuckoo hashing guarantee O(1) lookups in presence of persistent hash collisions

Most hash table implementations guarantee O(1) average case but O(n) maximum case for lookup (where 'n' is the number of keys in the table). But Cuckoo Hashing is described as O(1) maximum. ...
11
votes
2answers
4k views

Time complexity of 2^sqrt(n)

I am solving an algorithm question and my analysis is that it would run on O(2^sqrt(n)). How big is that? Does it equate to O(2^n)? Is it still non-polynomial time?
2
votes
2answers
3k views

Merge sort and O(n log n) mystery

I read every explanation here but still not convinced. I think mergesort is n * n and I know I am wrong but not sure where. Here is what I think: Suppose we are sorting 8 elements and this is the ...
1
vote
1answer
1k views

How should I express the complexity of two nested loops over different datasets in Big O notation?

I'm more or less teaching myself big O notation, so please forgive me if this is a duplicate of a question which applied to my question without me having the wisdom to realise it. For my own amusement/...
1
vote
3answers
270 views

Big O Notation of an example

My professor gave this example in a lecture: Example: Given an integer N, print out the values 1…N. for (int i=1; i<=N; i=i+1) { System.out.print(i); } The professor said that the loop was ...
46
votes
4answers
51k views

Trying to understand P vs NP vs NP Complete vs NP Hard

I am trying to understand these classifications and why they exist. Is my understanding right? If not, what? P is polynomial complexity, or O(nk) for some non-negative real number k, such as O(1), O(...
-1
votes
1answer
358 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))....
2
votes
1answer
575 views

How to sort a list containing bounded set of values in linear time when length is unknown?

Given a list of integers whose length is unknown, and each of its elements lies between 1 to 1000, how does one sort this list in linear time?
6
votes
2answers
4k views

What is time complexity of update in binary heap?

For a binary heap we have O(log(n)) for insert, O(log(n)) for delete min and heap construction can be done in O(n). In the context of using a binary heap in Djikstra, my exam paper involved an "...
2
votes
1answer
576 views

Time Complexity when Loop Variable Depends upon Outer Loop Variable

What is the time complexity of the following piece of code in worst case? s = 0; for( i = 1; i <= n; ++i ) { for( j = 1; j <= i * i; j++ ) { for( k = 1; k <= j and j % i == 0; k++...