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.
big-o
6,835
questions
5373
votes
43
answers
831k
views
What is a plain English explanation of "Big O" notation?
I'd prefer as little formal definition as possible and simple mathematics.
- 61.8k
2733
votes
32
answers
1.6m
views
What does O(log n) mean exactly?
I am learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm ...
- 107k
978
votes
24
answers
536k
views
Big O, how do you calculate/approximate it?
Most people with a degree in CS will certainly know what Big O stands for.
It helps us to measure how well an algorithm scales.
But I'm curious, how do you calculate or approximate the complexity of ...
- 18.3k
877
votes
19
answers
497k
views
How can building a heap be O(n) time complexity?
Can someone help explain how can building a heap be O(n) complexity?
Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the ...
- 17.8k
526
votes
8
answers
130k
views
What is Constant Amortized Time?
What is meant by "Constant Amortized Time" when talking about time complexity of an algorithm?
- 6,207
467
votes
9
answers
235k
views
What is the difference between Θ(n) and O(n)?
Sometimes I see Θ(n) with the strange Θ symbol with something in the middle of it, and sometimes just O(n). Is it just laziness of typing because nobody knows how to type this symbol, or does it mean ...
- 17.9k
441
votes
5
answers
375k
views
Difference between Big-O and Little-O Notation
What is the difference between Big-O notation O(n) and Little-O notation o(n)?
- 7,271
417
votes
7
answers
464k
views
Determining complexity for recursive functions (Big O notation)
I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve these ...
- 4,849
395
votes
12
answers
422k
views
Computational complexity of Fibonacci Sequence
I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci ...
- 81k
391
votes
4
answers
99k
views
List of Big-O for PHP functions
After using PHP for a while now, I've noticed that not all built-in PHP functions are as fast as expected. Consider these two possible implementations of a function that finds if a number is prime ...
- 43.5k
365
votes
33
answers
81k
views
Are there any O(1/n) algorithms?
Are there any O(1/n) algorithms?
Or anything else which is less than O(1)?
321
votes
25
answers
43k
views
Big-O for Eight Year Olds? [duplicate]
I'm asking more about what this means to my code. I understand the concepts mathematically, I just have a hard time wrapping my head around what they mean conceptually. For example, if one were to ...
- 195k
275
votes
10
answers
311k
views
Is log(n!) = Θ(n·log(n))?
I am to show that log(n!) = Θ(n·log(n)).
A hint was given that I should show the upper bound with nn and show the lower bound with (n/2)(n/2). This does not seem all that intuitive to me. Why would ...
- 6,203
257
votes
17
answers
310k
views
Append an object to a list in R in amortized constant time, O(1)?
If I have some R list mylist, you can append an item obj to it like so:
mylist[[length(mylist)+1]] <- obj
But surely there is some more compact way. When I was new at R, I tried writing lappend(...
- 21.8k
251
votes
23
answers
19k
views
Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
Are there are any cases where you would prefer O(log n) time complexity to O(1) time complexity? Or O(n) to O(log n)?
Do you have any examples?
- 2,708
235
votes
32
answers
251k
views
How to find the kth largest element in an unsorted array of length n in O(n)?
I believe there's a way to find the kth largest element in an unsorted array of length n in O(n). Or perhaps it's "expected" O(n) or something. How can we do this?
- 44k
220
votes
7
answers
199k
views
What exactly does big Ө notation represent?
I'm really confused about the differences between big O, big Omega, and big Theta notation.
I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big Ө (...
- 2,263
202
votes
26
answers
175k
views
Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)? [closed]
My co-workers took me back in time to my University days with a discussion of sorting algorithms this morning. We reminisced about our favorites like StupidSort, and one of us was sure we had seen a ...
198
votes
4
answers
244k
views
Big-O summary for Java Collections Framework implementations? [closed]
I may be teaching a "Java crash-course" soon. While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the ...
- 25.7k
190
votes
15
answers
167k
views
Is a Java hashmap search really O(1)?
I've seen some interesting claims on SO re Java hashmaps and their O(1) lookup time. Can someone explain why this is so? Unless these hashmaps are vastly different from any of the hashing algorithms I ...
- 868k
187
votes
16
answers
239k
views
What does "O(1) access time" mean? [duplicate]
I have seen this term "O(1) access time" used to mean "quickly" but I don't understand what it means. The other term that I see with it in the same context is "O(n) access time". Could someone please ...
Grygori
186
votes
6
answers
41k
views
Are 2^n and n*2^n in the same time complexity?
Resources I've found on time complexity are unclear about when it is okay to ignore terms in a time complexity equation, specifically with non-polynomial examples.
It's clear to me that given ...
- 2,643
183
votes
3
answers
151k
views
What are the complexity guarantees of the standard containers?
Apparently ;-) the standard containers provide some form of guarantees.
What type of guarantees and what exactly are the differences between the different types of container?
Working from the SGI page ...
- 261k
176
votes
30
answers
321k
views
How to merge two sorted arrays into a sorted array? [closed]
This was asked of me in an interview and this is the solution I provided:
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
...
- 4,260
176
votes
31
answers
22k
views
O(nlogn) Algorithm - Find three evenly spaced ones within binary string
I had this question on an Algorithms test yesterday, and I can't figure out the answer. It is driving me absolutely crazy, because it was worth about 40 points. I figure that most of the class didn'...
168
votes
15
answers
90k
views
Why is inserting in the middle of a linked list O(1)?
According to the Wikipedia article on linked lists, inserting in the middle of a linked list is considered O(1). I would think it would be O(n). Wouldn't you need to locate the node which could be ...
- 20.9k
161
votes
3
answers
233k
views
Time complexity of python set operations?
What is the the time complexity of each of python's set operations in Big O notation?
I am using Python's set type for an operation on a large number of items. I want to know how each operation's ...
- 10.8k
154
votes
12
answers
268k
views
Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
What are some algorithms which we use daily that has O(1), O(n log n) and O(log n) complexities?
- 102k
139
votes
10
answers
66k
views
Can hash tables really be O(1)?
It seems to be common knowledge that hash tables can achieve O(1), but that has never made sense to me. Can someone please explain it? Here are two situations that come to mind:
A. The value is an ...
- 53.6k
131
votes
20
answers
87k
views
Maximum single-sell profit
Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay ...
- 8,472
129
votes
8
answers
192k
views
Understanding Time complexity calculation for Dijkstra Algorithm
As per my understanding, I have calculated time complexity of Dijkstra Algorithm as big-O notation using adjacency list given below. It didn't come out as it was supposed to and that led me to ...
- 10.3k
127
votes
2
answers
48k
views
What is pseudopolynomial time? How does it differ from polynomial time?
What is pseudopolynomial time? How does it differ from polynomial time? Some algorithms that run in pseudopolynomial time have runtimes like O(nW) (for the 0/1 Knapsack Problem) or O(√n) (for ...
- 367k
126
votes
2
answers
48k
views
Big O of JavaScript arrays
Arrays in JavaScript are very easy to modify by adding and removing items. It somewhat masks the fact that most languages arrays are fixed-size, and require complex operations to resize. It seems that ...
- 43.8k
123
votes
3
answers
127k
views
What would cause an algorithm to have O(log log n) complexity?
This earlier question addresses some of the factors that might cause an algorithm to have O(log n) complexity.
What would cause an algorithm to have time complexity O(log log n)?
- 367k
120
votes
11
answers
131k
views
Time complexity of Euclid's Algorithm
I am having difficulty deciding what the time complexity of Euclid's greatest common denominator algorithm is. This algorithm in pseudo-code is:
function gcd(a, b)
while b ≠ 0
t := b
...
- 10.4k
119
votes
7
answers
144k
views
What is the difference between lower bound and tight bound?
With the reference of this answer, what is Theta (tight bound)?
Omega is lower bound, quite understood, the minimum time an algorithm may take. And we know Big-O is for upper bound, means the maximum ...
- 39.7k
119
votes
7
answers
64k
views
Is Big O(logn) log base e?
For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural ...
- 2,158
117
votes
15
answers
19k
views
Is this technically an O(1) algorithm for "Hello World"?
Would this be classified as an O(1) algorithm for "Hello, World!" ??
public class Hello1
{
public static void Main()
{
DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( ...
- 3,230
113
votes
6
answers
80k
views
What would cause an algorithm to have O(log n) complexity?
My knowledge of big-O is limited, and when log terms show up in the equation it throws me off even more.
Can someone maybe explain to me in simple terms what a O(log n) algorithm is? Where does the ...
- 3,795
93
votes
16
answers
107k
views
Example of O(n!)?
What is an example (in code) of a O(n!) function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.
- 1,179
90
votes
7
answers
146k
views
Difference between O(n) and O(log(n)) - which is better and what exactly is O(log(n))?
This is my first course in data structures and every lecture / TA lecture , we talk about O(log(n)) . This is probably a dumb question but I'd appreciate if someone can explain to me exactly what does ...
- 21.6k
87
votes
4
answers
57k
views
What is the complexity of regular expression?
What is the complexity with respect to the string length that takes to perform a regular expression comparison on a string?
- 14.6k
84
votes
12
answers
122k
views
Why is O(n) better than O( nlog(n) )?
I just came around this weird discovery, in normal maths, n*logn would be lesser than n, because log n is usually less than 1.
So why is O(nlog(n)) greater than O(n)? (ie why is nlogn considered to ...
- 3,378
84
votes
4
answers
89k
views
Python dictionary keys. "In" complexity
Quick question to mainly satisfy my curiosity on the topic.
I am writing some large python programs with an SQlite database backend and will be dealing with a large number of records in the future, ...
- 4,416
84
votes
11
answers
31k
views
Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
I came across this question:
Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
I initially thought of using a min-heap data structure which has O(1) ...
- 8,220
82
votes
9
answers
34k
views
Why is accessing an element of a dictionary by key O(1) even though the hash function may not be O(1)?
I see how you can access your collection by key. However, the hash function itself has a lot of operations behind the scenes, doesn't it?
Assuming you have a nice hash function which is very ...
- 1,419
81
votes
2
answers
77k
views
multiset, map and hash map complexity
I would like to know the complexity in Big O notation of the STL multiset, map and hash map classes when:
inserting entries
accessing entries
retrieving entries
comparing entries
Harry
77
votes
8
answers
166k
views
what does O(N) mean [duplicate]
Possible Duplicate:
What is Big O notation? Do you use it?
Hi all,
fairly basic scalability notation question.
I recently recieved a comment on a post that my python ordered-list implimentation
...
- 7,609
74
votes
4
answers
68k
views
Big-O of list slicing
Say I have some Python list, my_list which contains N elements. Single elements may be indexed by using my_list[i_1], where i_1 is the index of the desired element. However, Python lists may also be ...
- 8,757
72
votes
8
answers
102k
views
What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?
What is the Big-O time complexity of the following nested loops:
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
System.out.println("i = " + i + " j = &...
- 92.1k