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
66
votes
17answers
14k views

Is big-O really that relevant when working in industry?

In every interview I have been in, I have been quizzed on mathematical analysis of complexity, including big-O notation. How relevant is big-O analysis to development in industry? How often do you ...
53
votes
11answers
18k views

Get 100 highest numbers from an infinite list

One of my friend was asked this interview question - "There is a constant flow of numbers coming in from some infinite list of numbers out of which you need to maintain a datastructure as to ...
51
votes
4answers
65k 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(...
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 ...
39
votes
20answers
7k views

Do real-world algorithms that greatly outperform in the class below exist? [closed]

Last night I was discussing with another programmer that even though something may be O(1), an operation which is O(n) may outperform it if there are is a large constant in the O(1) algorithm. He ...
32
votes
2answers
11k views

What is O(…) and how do I calculate it?

Help! I have a question where I need to analyze the Big-O of an algorithm or some code. I am unsure exactly what Big-O is or how it relates to Big-Theta or other means of analyzing an algorithm's ...
31
votes
5answers
52k views

Is this a Proper “Rule” for Identifying the “Big O” Notation of an Algorithm?

I've been learning more about Big O Notation and how to calculate it based on how an algorithm is written. I came across an interesting set of "rules" for calculating an algorithms Big O notation and ...
30
votes
5answers
185k views

Why is mergesort O(log n)?

Mergesort is a divide and conquer algorithm and is O(log n) because the input is repeatedly halved. But shouldn't it be O(n) because even though the input is halved each loop, each input item needs to ...
27
votes
5answers
62k views

Determining if an Algorithm is O (log n)

I'm refreshing my CS Theory, and I want to know how to identify that an algorithm O (log n) complexity. Specifically, is there an easy way to identify it? I know with O(n), you usually have a single ...
26
votes
7answers
14k views

What is O in Big O?

What is Big and O in Big O notation? I've read the definitions and it doesn't tell what is O pronounced as 'oh'. For example - I understand that O(n) is complexity of a linear algorithm where n could ...
24
votes
5answers
25k views

Algorithms: How do I sum O(n) and O(nlog(n)) together?

I have the follow algorithm which finds duplicates and removes them: public static int numDuplicatesB(int[] arr) { Sort.mergesort(arr); int numDups = 0; for (int i = 1; i < arr.length; ...
24
votes
2answers
21k views

Algorithm to merge two sorted arrays with minimum number of comparisons

Given are two sorted arrays a, b of type T with size n and m. I am looking for an algorithm that merges the two arrays into a new array (of maximum size n+m). If you have a cheap comparison ...
22
votes
4answers
3k views

When speaking, how can I say that the time complexity order of an algorithm is O(N log N)?

What term can I use to describe something with O(N log N) complexity? For example: O(1): Constant O(log N): Logarithmic O(N): Linear O(N log N): ?????? O(N2): Quadratic O(N3): Cubic
22
votes
2answers
5k views

Why is Big O taught instead of Big Theta?

Big O notation provides an upper bound to a function whereas Big Theta provides a tight bound. However I find that Big O notation is typically (and informally) taught and used when they really mean ...
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 ...
16
votes
9answers
26k views

Big O Question about an algorithm with (n^2 + n) / 2 growth rate

I'm asking this question because I am confused about one aspect regarding big O notation. I am using the book, Data Structures and Abstractions with Java by Frank Carrano. In the chapter on the "...
15
votes
6answers
6k views

How do I determine the runtime of a double recursive function?

Given any arbitrarily double-recursive function, how would one calculate its run time? For Example (in pseudocode): int a(int x){ if (x < = 0) return 1010; else return b(x-1) + a(x-1);...
13
votes
7answers
8k views

Big Oh notation does not mention constant value

I am a programmer and have just started reading Algorithms. I am not completely convinced with the notations namely Bog Oh, Big Omega and Big Theta. The reason is by definition of Big Oh, it states ...
12
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?
12
votes
3answers
3k views

Please explain the statement that the function an+b belongs to O(n^2) and Θ(n)?

Let's say I have a linear function f(n)= an+b, what is the best way to prove that this function belongs to O(n2) and Θ(n)? I do not need mathematical rigor here. I need a programmers answer. Some ...
11
votes
5answers
854 views

Programmaticaly finding the Landau notation (Big O or Theta notation) of an algorithm?

I'm used to search for the Landau (Big O, Theta...) notation of my algorithms by hand to make sure they are as optimized as they can be, but when the functions are getting really big and complex, it's ...
10
votes
2answers
5k views

Big O equivalence for LINQ select

I'm trying to determine if there is a change in the Big O equivalence of a nested loop when I use a LINQ select instead. public void myFunc(List<Foo> fooList, List<Bar> barList) { ...
8
votes
2answers
2k views

single for-loop runtime explanation problem

I am analyzing some running times of different for-loops, and as I'm getting more knowledge, I'm curious to understand this problem which I have still yet to find out. I have this exercise called "How ...
8
votes
4answers
8k views

Big-O for nested loop

I am reading this post on Big-O It says that the following code is O(n^2): bool ContainsDuplicates(String[] strings) { for(int i = 0; i < strings.Length; i++) { for(int j = 0; j &...
8
votes
3answers
499 views

Change of the complexity class through compiler optimization?

I am looking for an example where an algorithm is apparently changing its complexity class due to compiler and/or processor optimization strategies.
7
votes
1answer
3k views

Problems Calculating Big-O Complexity

I'm a complete beginner to Java, only in my second quarter of classes. I'm having trouble understanding our current chapter about calculating big-O for methods. So I thought I was right in saying that ...
7
votes
2answers
3k views

Space complexity of Iterative Deepening DFS

We read on Wikipedia > Iterative deepening depth-first search that The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal. Wikipedia also ...
6
votes
2answers
5k 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 "...
5
votes
8answers
3k views

How meaningful is the Big-O time complexity of an algorithm?

Programmers often talk about the time complexity of an algorithm, e.g. O(log n) or O(n^2). Time complexity classifications are made as the input size goes to infinity, but ironically infinite input ...
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 ...
5
votes
3answers
4k views

Loop runtime question

I had an exam today and I feel that I did pretty well, except I could not for the life of me figure out what appears to be an unbelievably simple question. We were asked to give theta notation run ...
5
votes
3answers
11k 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 ...
5
votes
2answers
10k views

What does 'upper bound' mean in context of BigO?

My computer science teacher says Big O has an upper bound but no lower bound. When I look at a graph of an algorithm mapped out using BigO though, there isn't an upper bound at all. The upper limit ...
4
votes
5answers
505 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. ...
4
votes
1answer
2k views

Quickest sorting algorithm for sorting a low number of integers

I am making a program on my spare time that I want to run as quickly as possible. The program is written in C. A large set of the procedures operate on pointers to 7 integers that are sorted by their ...
4
votes
1answer
2k views

why adding a vertex in a graph represented using an adjacency matrix takes O(|v|^2) time complexity?

Adding a vertex in a graph that is represented using an adjacency matrix takes O(|v|^2) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency matrix > add vertex). But ...
4
votes
3answers
11k 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]+.....
4
votes
1answer
663 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. ...
3
votes
3answers
12k views

Why is the complexity of fetching a value from an array be O(1)?

How come the complexity of fetching a value from an array by it's index is O(1)? I thought the algorithm has to go through all the indexes, find the correct index, and then know what value to return. ...
3
votes
4answers
17k views

Time-complexity of nested for loop

I have loops like this: for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { sum += 1; } } It's O(n * ), but I'm not sure what the j < i loop is. I have some tests ...
3
votes
2answers
37k views

Running time of simple for-loops

I'm reading algorithms and I understand most of it, one thing that I can still struggle with a lot is something as simple as running times on different for-loops. Everyone seems to have easy with that,...
3
votes
3answers
397 views

questions on a particular algorithm

Upon searching for a fast primr algorithm, I stumbled upon this: public static boolean isP(long n) { if (n==2 || n==3) return true; if ((n&0x1)==0 || n%3==0 || n<2) return false; ...
3
votes
3answers
628 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
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(...
3
votes
1answer
284 views

Big-O for Immutable Trees

How would you calculate the time and space complexity for a tree algorithm that creates a copy of a tree, but reuses as much of the original tree as possible? For example, A /|\ B C G /|\ D ...
3
votes
1answer
158 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,...
3
votes
2answers
722 views

Big O Nested For Loop Breakdown

I understand how to get a general picture of the big O of a nested loop, but what would be the operations for each loop in a nested for loop? If we have: for(int i=0; i<n; i++) { for(int j=i+...
3
votes
1answer
987 views

What is the time complexity of this program?

An algorithm is given on GeeksForGeeks.com for constructing a Binary Search Tree from its preorder traversal. They say that the time complexity for the following code is O(n^2). But in my opinion it ...
2
votes
2answers
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 ...
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 ...