Software Engineering Stack Exchange
Software Engineering Stack Exchange

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.

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.

Other Questions

Further Reading

135 questions
67
votes
17 answers

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 really use it, and how necessary is it to have a…
MM01
  • 1,373
  • 2
  • 14
  • 13
62
votes
4 answers

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(n1/2), O(n2), O(n3), etc. If a problem belongs to…
Nakano
  • 731
  • 1
  • 6
  • 7
53
votes
11 answers

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 return the top 100 highest numbers at any given point…
Sachin Shanbhag
  • 543
  • 1
  • 4
  • 7
50
votes
8 answers

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 this is, but I'm struggling to follow. I wonder…
SteveJ
  • 636
  • 5
  • 10
41
votes
2 answers

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 complexity. I am unsure whether Big-O refers to the…
mowwwalker
  • 1,117
  • 2
  • 12
  • 20
39
votes
20 answers

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

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 disagreed, so I've brought it here. Are there…
KyleWpppd
  • 278
  • 3
  • 7
38
votes
5 answers

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 be iterated on to do the swapping in each halved…
perseverance
  • 575
  • 3
  • 7
  • 9
33
votes
5 answers

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 loop; O(n^2) is a double loop; O(n^3) is a triple…
Atif
  • 915
  • 1
  • 6
  • 12
31
votes
5 answers

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 I wanted to see if I'm on the right track or way…
Levi Hackwith
  • 843
  • 1
  • 7
  • 13
31
votes
7 answers

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 be the number of operations. but what is an O?
Karen15
  • 329
  • 1
  • 3
  • 4
30
votes
5 answers

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; i++) { if (arr[i] == arr[i - 1]) { …
chopper draw lion4
  • 577
  • 2
  • 6
  • 8
25
votes
2 answers

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 Big Theta. e.g. "Quicksort is O(N^2)" can turned…
tskuzzy
  • 732
  • 1
  • 7
  • 12
25
votes
2 answers

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 operation, this is pretty simple. Just take from the array…
Rüdiger Klaehn
  • 369
  • 1
  • 3
  • 7
23
votes
4 answers

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
matiascelasco
  • 385
  • 2
  • 10
19
votes
6 answers

What do you call it when you change the Big O execution time of a function

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 runs, while keeping the return values and inputs…
Code Whisperer
  • 723
  • 6
  • 10
1
2 3
…
8 9