7 ms·

Big-O Misconceptions

62 points by denzil_correa 14y ago

buro9 14y ago
The biggest misconception I ever came across was during a job interview in which I was the interviewee. After explaining skip-lists and sketching up the Big-O complexities for best and worst case for sorted and unsorted data... the interviewer turned to me and asked why wouldn't I use a skip-list (it should already have rung bells that it wasn't "in which instances might you not use"). My answer was that each problem should be understood in terms of the data and task before choosing a data structure and algorithm. That answer was rejected. The interviewers answer: "No, you shouldn't use skip lists because the memory of all those extra pointers is too much for the JVM." The biggest misconception I've come across is that Big-O says anything at all about the language you're coding in and your implementation. I did point this out, but was shot down pretty fast. The company in that scenario was AWS, the position was architect level. I didn't take the job. Interestingly they offered me another job different from the one that I had been interviewed devoid of any product dev at all on the basis that I was "too technical" for any role that included product. Big-O doesn't care for your implementation.
- jiggy2011 14y ago
  Weird, I don't quite understand how the pointers would be "too much for the JVM". I suppose this will depend on how many layers your skip list has and how big it is etc. Is there some reason (related to GC or whatever?) that it is bad in particular to use pointer heavy data structures on the JVM?
  - buro9 14y ago
    I questioned the same thing, but he answered with "the list might have millions of items". Java isn't my strong point but I struggled to think how it might be an issue. Interviews aren't the place to possibly end up making the interviewer look foolish. I just let it go. If I was working with him I'd say "Show me". As I'm still curious as to whether it makes any difference. Wasn't the point though, Big-O still doesn't care about the implementation.
    - dbaupp 14y ago
      Java isn't my strong point either, so this is more of a question than an answer. But Java is built around objects (and so everything is a pointer), so the JVM is designed to work with pointer-heavy code, I would think. (Or is that incorrect?)
      - jiggy2011 14y ago
        Java does have primitive types like int , char etc which I believe are stack allocated. Java programmers do like to "box" these into classes like "Integer" etc though. What I find confusing about the answer is that it implies that there is some reason that a skip list (compared to another structure) would be particularly inefficient in the JVM (compared to say native C++). Basically a skip list will cost you some extra memory by storing more pointers which allow you to "skip" ahead the list but as you add extra layers each layer will have less pointers than the one below it. A skip list might be a bad idea if you are working a severely memory constrained system and saving memory is more important than lookup speed on your data structure. They would also of course be a bad idea if there is another structure better suited to what you are doing (B tree or whatever). But saying "Skip lists are bad because there are too many pointers for Java" just seems like a big wtf to me, unless there is something I am missing here.
        Espressosaurus 14y ago
        While he worded it poorly, he is correct. Kinda. In a skip list with millions of items, you're going to have something like n log(n) SkipListObjects. The references are virtually free. The objects are not. On a typical JVM implementation, each object takes ~100 bytes. IIRC even an empty ArrayList will cost you something like 60-80 bytes. If the extra log(n) of space complexity is going to make a difference, then a skip list might not make sense. But honestly, if you've got millions of objects, you might want to consider a different language/environment. Java is pretty fast these days, but it will still chew up considerably more memory than most native solutions.
        14y ago
- vph 14y ago
  Based on your testimony, it seems the interviewer did not ask you a question about big-O, and you thought he did.
  - buro9 14y ago
    No, he did. The question was roughly: "As you seem to like algorithms could you explain what skip lists are, draw on the whiteboard if necessary.". After that came, "Now, using Big-O, explain why this could be better than a normal linked list". Before finally the "Why wouldn't you use skip lists?" and that classic answer. And there were 2 interviewers in the room. One was leading and the other was observing and learning how to interview.
    - cube13 14y ago
      >Before finally the "Why wouldn't you use skip lists?" and that classic answer. That answer was a non-answer, though. Saying "You pick the best structure for the data" doesn't answer the question "Why would you not use a skiplist". A few reasons, off the top of my head: 1. Size of the list structures can get gigantic, especially as the total size of the list increases. This is especially true with 64-bit pointers, and small data(ASCII names, integers, etc.). 2. While the list is very good(O(log n) ) for searches, additions and deletions can be problematic, especially if they're more common than lookups. 3. Depending on the implementation/language, it might be a good idea to pre-allocate the pointer array. Increasing the list size above the supported pointer array size can be a major headache.
btilly 14y ago
This is a worthy attempt, but the horse has already left the barn. Programmers everywhere understand big-O to mean what big-Theta should mean. And since O is easier to type than Θ and Θ is the more useful concept, this will not change. Given that language is defined by usage, you need to figure out what usage the other person likely has, and work with that. I will happily use the correct notation with people who understand it, but don't bother complaining about incorrect use of the notation from people who will never have reason to care.
- Aardwolf 14y ago
  I agree. Nobody is ever going to attempt to write the theta in ASCII or bother typing it given that it's not on most keyboards. Math and practical programming are different worlds, each with their own notations. Programmers are quite used to using ASCII. Also, if someone says "My algorithm is O(n log n)", doesn't it make sense that he means both the lower and upper bound? Even if technically correct, you wouldn't say "My algorithm is O(n^100)" when it's O(n log n). It's an English language thing... P.S. I didn't read the article because it's not loading, but can kind of guess the context from your response and noticed this problem before.
- sesqu 14y ago
  I'm not sure I agree that Θ is more useful than Ο; rather, I think Ο∘E, the expected (time) complexity, is most useful. Take quicksort for example (see misconception 4). Few people care that it's Ο(n²), and even fewer bother to ask if the implementation is Ω(1). It's not even Θ anything. Yet it's one of the canonical examples of complexity analysis, with the understanding that most people are really concerned with average performance.
  - btilly 14y ago
    Ironic, you just illustrated misconceptions #3 and #4, while trying to educate me about why I was wrong to comment on misconception #2. All of these notations are just notations for functions, and the functions can have any relation to reality that you want. Here are precise and accurate statements about quicksort using Θ notation. The average and best case performance of quicksort is Θ(n log(n)). The worst case performance of quicksort is Θ(n²). I maintain that most decent hackers would make those same statements using O notation (which is true), but many would jump to correct someone who said that the expected performance of quicksort is O(n²). According to what is taught in CS, that "correction" is wrong. But given that language is established by usage, they aren't really wrong. And given that arbitrary upper bounds aren't very useful, the common usage makes sense. Before disagreeing, tell me what value there is in the true statement that the expected run time of all major sorting algorithms is O(nⁿ).
deleted 14y ago
[deleted]
adrianr 14y ago
Misconception 4 should be the first.
gsibble 14y ago
The biggest misconception of Big-O is that it actually matters at most start-ups. I get asked about Big-O all the time. My response is, "You haven't launched. You have zero traction. You have no users yet. Stop worrying about Big-O and just build the damn product."
- jrockway 14y ago
  This attitude is the reason why the most iconic image related to Twitter is the fail whale.
  - recursive 14y ago
    Better to be twitter with a fail whale than app.ly-ify'r with no users, but awesome scalability.
- xsmasher 14y ago
  If a startup is thinking short-term, then they'll ask technical/tactical questions. Explain X command or language/os feature. Find out what the candidate knows now. Like you implied, strategy doesn't matter if you're dead. If they're thinking long-term, they'll ask theoretical/strategic questions to assess general education level (traditional or self-taught) and ability to adapt. What will the candidate will be like in three to five years? Talking about algorithms and complexity can help there. You don't know what tech/language you'll be using in the future, but fundamentals will still apply. Neither one should be asking you questions about light bulbs or where to bury the survivors.
maeon3 14y ago
The equals sign in the big-O notation makes about as much sense as the folowing mathamatical expression: Pidgeons = arraylist(1, ..., n) It is an exercise in nonsense, it helps young computer scientists unwravel nonsense in the world by making it part of the curriculum. Sure big-o notation can be useful, but using equations to describe it is like trying to type with boxing gloves.
flebron 14y ago
I wrote this as a comment there, but I'll repaste it here since it's not showing up. ----------- One other thing I'd like to add, when considering asymptotic analysis, one needs to take into account both the cost model (i.e. what is assumed about the cost of operations) and the input size (i.e. what the variables mean). So for instance, if I tell you that the following program to find a number's divisors is O(n) operations, I wouldn't necessarily be wrong: for(i = 1; i <= n; ++i) if(n % i == 0) printf("%d\n", i); After all, this is doing a single loop, and it will loop exactly n times. So why isn't factoring a solved problem? We can factor numbers "in polynomial time!", I'll just check this list! Factoring, as a problem, is measured using bit complexity. That is, the input size is the number of bits needed to store the number I want to factor. So my program is actually O(2^m) operations, where m is the input size. And so this isn't factoring "in linear time", I just misunderstood what the input size was. Likewise, one can do analyses where the operation cost (also called computational model) is different from the uniform model. If I am doing crypto, using GMP, it would not be smart to say that adding any two GMP integers is O(1) operations, like we assume with our standard model of costs, where adding integers is O(1). We can certainly assume that, and call that a basic operation, but we will see the number of operations and time it takes to be wildly different, so one should use an analysis where the cost of adding, say, the numbers n and m, is O(log n + log m) operations for instance, if one wants operation-counting analyses to give a hint at runtime. It is important to remember that it is the analyst who defines what operations are basic, and one can do analysis of the same algorithm in different cost models, to get different information about it. So asymptotic analyses of algorithms depend on both the input size, and the cost model. My divisors finding algorithm, for instance, is best measured using the logarithmic model of computation, and logarithmic input size. As a trick, it's fun to try to construct two functions f:N -> N, g:N -> N, such that neither f is O(g), nor g is O(f). Bonus points if they're both monotonically increasing. :) It's useful to dispel the notion that functions are given a total order by big-O notation.
tylerneylon 14y ago
For folks who genuinely love math (I do!), there's a great but little-known book by Hardy called Orders of Infinity that can help readers grok the possibilities of big-oh notation. It's not about algorithms, but about getting a solid understanding of the many ways functions can behave as n goes to infinity. As a bonus, it's a short (< 100 page) book. If you're more of a CS person than a mathy, I recommend Sipser's Introduction to the Theory of Computation. This one is written in friendly yet precise terms, and I found it a pleasure to read.
bnegreve 14y ago
I find this a too informal and ultimately confusing. > Misconception 1: “The Equals Sign Means Equality” The equal sign does mean equals. > The left-hand-side is a function, the right-hand-side is a … what, exactly? There is no help to be found in the definition. It just says “we write” without concerning itself with the fact that what “we write” is total nonsense. This is not clear at all ! > If you take it at face value, you can deduce that since 5n and 3n are both equal to O(n), then 3n must be equal to 5n and so 3=5. Yes well, f(x) = f(y) does not implies x = y. I think people know this .. ... and so on
- tsahyt 14y ago
  > The equal sign does mean equals. Yes. This is why using it with Big-O notation is formally wrong when we're being pedantic.
- lmkg 14y ago
  > The equal sign does mean equals. In the particular case of big-O notation, the equals sign does not mean equals. Trying to parse the equal sign literally leads to confusing and contradictory interpretations (which is why their explanation is confusion). You're misunderstanding the 3=5 example. Let f(n)=3n, let g(n)=5n. Using big-O notation, f(n)=O(n), g(n)=O(n). Were the equal sign behaving normally, then O(n) would be a single well-defined object, and one could use transitivity to conclude that 3n=5n. But of course this is false, because O(n) isn't a single function, nor really something that other functions can equal. It's a class of functions, not a function itself. It would be more appropriate to say that "f(n) belongs to O(n)," or more compactly, "f(n) ∈ O(n)." This is much closer to the real definition, and behaves appropriately when taken literally.
- esrauch 14y ago
  > This is not clear at all ! He is using 'type check' to point out the flaw. x = y means x and y are the same thing. If x is a function and y is an integer, then it can't possibly hold that x = y. Consider x = O(n). The implication would be that whatever type of thing O(n) is, x also is. This is trivially untrue. If x = y, and x is a function, then x(K) = y(K). It would be ridiculous to say that x(K) = O(n)(k). > Yes well, f(x) = f(y) does not implies x = y. I think people know this .. I don't understand why you are mentioning that. The issue is that x = f(z) and y = f(z), then x = y. You can't get two different values by applying the same function to the same value. Saying that f is O(n), the "is" is not an equality statement at all, "is" is some other function exactly as you mention that people understand. It is clearly some function that is non-transitive. In this case the relationship is most easily expressed using existing operators by having O(n) be a set of functions and the "is" in that sentence be the "exists-in" set operator, which is a case where the transitive property doesn't hold. Using the = symbol in that context is just bizarre when = is a otherwise always used to mean equality, which is function with special properties that don't apply here.
ambrop7 14y ago
Fun fact: there exist pairs of positive monotonic functions f(x) and g(x) such that neither f(x)=O(g(x)) nor g(x)=O(f(x)), i.e. the functions are not comparable asymptotically. Example: f(x)=gamma(floor(x)+1) (=floor(x)!) g(x)=gamma(floor(x-0.5)+1.5) There exists no such constant M>0 that f(x)<M*g(x) for x from some point on, and the converse. The two functions periodically cross each other in a way that neither is asymptotically bound by the other.
oskarkv 14y ago
The correct statement about lower bounds is this: "In the worst case, any comparison based sorting algorithm must make Ω(n log(n)) comparisons." You are making the same mistake that people that have Misconception 1 make. "The algorithm must make <a set of functions> comparisons." is a nonsensical statement.

62 points by denzil_correa 14y ago

buro9 14y ago

The biggest misconception I ever came across was during a job interview in which I was the interviewee. After explaining skip-lists and sketching up the Big-O complexities for best and worst case for sorted and unsorted data... the interviewer turned to me and asked why wouldn't I use a skip-list (it should already have rung bells that it wasn't "in which instances might you not use"). My answer was that each problem should be understood in terms of the data and task before choosing a data structure and algorithm. That answer was rejected. The interviewers answer: "No, you shouldn't use skip lists because the memory of all those extra pointers is too much for the JVM." The biggest misconception I've come across is that Big-O says anything at all about the language you're coding in and your implementation. I did point this out, but was shot down pretty fast. The company in that scenario was AWS, the position was architect level. I didn't take the job. Interestingly they offered me another job different from the one that I had been interviewed devoid of any product dev at all on the basis that I was "too technical" for any role that included product. Big-O doesn't care for your implementation.

jiggy2011 14y ago
Weird, I don't quite understand how the pointers would be "too much for the JVM". I suppose this will depend on how many layers your skip list has and how big it is etc. Is there some reason (related to GC or whatever?) that it is bad in particular to use pointer heavy data structures on the JVM?
- buro9 14y ago
  I questioned the same thing, but he answered with "the list might have millions of items". Java isn't my strong point but I struggled to think how it might be an issue. Interviews aren't the place to possibly end up making the interviewer look foolish. I just let it go. If I was working with him I'd say "Show me". As I'm still curious as to whether it makes any difference. Wasn't the point though, Big-O still doesn't care about the implementation.
  - dbaupp 14y ago
    Java isn't my strong point either, so this is more of a question than an answer. But Java is built around objects (and so everything is a pointer), so the JVM is designed to work with pointer-heavy code, I would think. (Or is that incorrect?)
    - jiggy2011 14y ago
      Java does have primitive types like int , char etc which I believe are stack allocated. Java programmers do like to "box" these into classes like "Integer" etc though. What I find confusing about the answer is that it implies that there is some reason that a skip list (compared to another structure) would be particularly inefficient in the JVM (compared to say native C++). Basically a skip list will cost you some extra memory by storing more pointers which allow you to "skip" ahead the list but as you add extra layers each layer will have less pointers than the one below it. A skip list might be a bad idea if you are working a severely memory constrained system and saving memory is more important than lookup speed on your data structure. They would also of course be a bad idea if there is another structure better suited to what you are doing (B tree or whatever). But saying "Skip lists are bad because there are too many pointers for Java" just seems like a big wtf to me, unless there is something I am missing here.
      - Espressosaurus 14y ago
        While he worded it poorly, he is correct. Kinda. In a skip list with millions of items, you're going to have something like n log(n) SkipListObjects. The references are virtually free. The objects are not. On a typical JVM implementation, each object takes ~100 bytes. IIRC even an empty ArrayList will cost you something like 60-80 bytes. If the extra log(n) of space complexity is going to make a difference, then a skip list might not make sense. But honestly, if you've got millions of objects, you might want to consider a different language/environment. Java is pretty fast these days, but it will still chew up considerably more memory than most native solutions.
        14y ago
vph 14y ago
Based on your testimony, it seems the interviewer did not ask you a question about big-O, and you thought he did.
- buro9 14y ago
  No, he did. The question was roughly: "As you seem to like algorithms could you explain what skip lists are, draw on the whiteboard if necessary.". After that came, "Now, using Big-O, explain why this could be better than a normal linked list". Before finally the "Why wouldn't you use skip lists?" and that classic answer. And there were 2 interviewers in the room. One was leading and the other was observing and learning how to interview.
  - cube13 14y ago
    >Before finally the "Why wouldn't you use skip lists?" and that classic answer. That answer was a non-answer, though. Saying "You pick the best structure for the data" doesn't answer the question "Why would you not use a skiplist". A few reasons, off the top of my head: 1. Size of the list structures can get gigantic, especially as the total size of the list increases. This is especially true with 64-bit pointers, and small data(ASCII names, integers, etc.). 2. While the list is very good(O(log n) ) for searches, additions and deletions can be problematic, especially if they're more common than lookups. 3. Depending on the implementation/language, it might be a good idea to pre-allocate the pointer array. Increasing the list size above the supported pointer array size can be a major headache.

btilly 14y ago

This is a worthy attempt, but the horse has already left the barn. Programmers everywhere understand big-O to mean what big-Theta should mean. And since O is easier to type than Θ and Θ is the more useful concept, this will not change. Given that language is defined by usage, you need to figure out what usage the other person likely has, and work with that. I will happily use the correct notation with people who understand it, but don't bother complaining about incorrect use of the notation from people who will never have reason to care.

Aardwolf 14y ago
I agree. Nobody is ever going to attempt to write the theta in ASCII or bother typing it given that it's not on most keyboards. Math and practical programming are different worlds, each with their own notations. Programmers are quite used to using ASCII. Also, if someone says "My algorithm is O(n log n)", doesn't it make sense that he means both the lower and upper bound? Even if technically correct, you wouldn't say "My algorithm is O(n^100)" when it's O(n log n). It's an English language thing... P.S. I didn't read the article because it's not loading, but can kind of guess the context from your response and noticed this problem before.
sesqu 14y ago
I'm not sure I agree that Θ is more useful than Ο; rather, I think Ο∘E, the expected (time) complexity, is most useful. Take quicksort for example (see misconception 4). Few people care that it's Ο(n²), and even fewer bother to ask if the implementation is Ω(1). It's not even Θ anything. Yet it's one of the canonical examples of complexity analysis, with the understanding that most people are really concerned with average performance.
- btilly 14y ago
  Ironic, you just illustrated misconceptions #3 and #4, while trying to educate me about why I was wrong to comment on misconception #2. All of these notations are just notations for functions, and the functions can have any relation to reality that you want. Here are precise and accurate statements about quicksort using Θ notation. The average and best case performance of quicksort is Θ(n log(n)). The worst case performance of quicksort is Θ(n²). I maintain that most decent hackers would make those same statements using O notation (which is true), but many would jump to correct someone who said that the expected performance of quicksort is O(n²). According to what is taught in CS, that "correction" is wrong. But given that language is established by usage, they aren't really wrong. And given that arbitrary upper bounds aren't very useful, the common usage makes sense. Before disagreeing, tell me what value there is in the true statement that the expected run time of all major sorting algorithms is O(nⁿ).

deleted 14y ago

[deleted]

adrianr 14y ago

Misconception 4 should be the first.

gsibble 14y ago

The biggest misconception of Big-O is that it actually matters at most start-ups. I get asked about Big-O all the time. My response is, "You haven't launched. You have zero traction. You have no users yet. Stop worrying about Big-O and just build the damn product."

jrockway 14y ago
This attitude is the reason why the most iconic image related to Twitter is the fail whale.
- recursive 14y ago
  Better to be twitter with a fail whale than app.ly-ify'r with no users, but awesome scalability.
xsmasher 14y ago
If a startup is thinking short-term, then they'll ask technical/tactical questions. Explain X command or language/os feature. Find out what the candidate knows now. Like you implied, strategy doesn't matter if you're dead. If they're thinking long-term, they'll ask theoretical/strategic questions to assess general education level (traditional or self-taught) and ability to adapt. What will the candidate will be like in three to five years? Talking about algorithms and complexity can help there. You don't know what tech/language you'll be using in the future, but fundamentals will still apply. Neither one should be asking you questions about light bulbs or where to bury the survivors.

maeon3 14y ago

The equals sign in the big-O notation makes about as much sense as the folowing mathamatical expression: Pidgeons = arraylist(1, ..., n) It is an exercise in nonsense, it helps young computer scientists unwravel nonsense in the world by making it part of the curriculum. Sure big-o notation can be useful, but using equations to describe it is like trying to type with boxing gloves.

flebron 14y ago

I wrote this as a comment there, but I'll repaste it here since it's not showing up. ----------- One other thing I'd like to add, when considering asymptotic analysis, one needs to take into account both the cost model (i.e. what is assumed about the cost of operations) and the input size (i.e. what the variables mean). So for instance, if I tell you that the following program to find a number's divisors is O(n) operations, I wouldn't necessarily be wrong: for(i = 1; i <= n; ++i) if(n % i == 0) printf("%d\n", i); After all, this is doing a single loop, and it will loop exactly n times. So why isn't factoring a solved problem? We can factor numbers "in polynomial time!", I'll just check this list! Factoring, as a problem, is measured using bit complexity. That is, the input size is the number of bits needed to store the number I want to factor. So my program is actually O(2^m) operations, where m is the input size. And so this isn't factoring "in linear time", I just misunderstood what the input size was. Likewise, one can do analyses where the operation cost (also called computational model) is different from the uniform model. If I am doing crypto, using GMP, it would not be smart to say that adding any two GMP integers is O(1) operations, like we assume with our standard model of costs, where adding integers is O(1). We can certainly assume that, and call that a basic operation, but we will see the number of operations and time it takes to be wildly different, so one should use an analysis where the cost of adding, say, the numbers n and m, is O(log n + log m) operations for instance, if one wants operation-counting analyses to give a hint at runtime. It is important to remember that it is the analyst who defines what operations are basic, and one can do analysis of the same algorithm in different cost models, to get different information about it. So asymptotic analyses of algorithms depend on both the input size, and the cost model. My divisors finding algorithm, for instance, is best measured using the logarithmic model of computation, and logarithmic input size. As a trick, it's fun to try to construct two functions f:N -> N, g:N -> N, such that neither f is O(g), nor g is O(f). Bonus points if they're both monotonically increasing. :) It's useful to dispel the notion that functions are given a total order by big-O notation.

tylerneylon 14y ago

For folks who genuinely love math (I do!), there's a great but little-known book by Hardy called Orders of Infinity that can help readers grok the possibilities of big-oh notation. It's not about algorithms, but about getting a solid understanding of the many ways functions can behave as n goes to infinity. As a bonus, it's a short (< 100 page) book. If you're more of a CS person than a mathy, I recommend Sipser's Introduction to the Theory of Computation. This one is written in friendly yet precise terms, and I found it a pleasure to read.

bnegreve 14y ago

I find this a too informal and ultimately confusing. > Misconception 1: “The Equals Sign Means Equality” The equal sign does mean equals. > The left-hand-side is a function, the right-hand-side is a … what, exactly? There is no help to be found in the definition. It just says “we write” without concerning itself with the fact that what “we write” is total nonsense. This is not clear at all ! > If you take it at face value, you can deduce that since 5n and 3n are both equal to O(n), then 3n must be equal to 5n and so 3=5. Yes well, f(x) = f(y) does not implies x = y. I think people know this .. ... and so on

tsahyt 14y ago
> The equal sign does mean equals. Yes. This is why using it with Big-O notation is formally wrong when we're being pedantic.
lmkg 14y ago
> The equal sign does mean equals. In the particular case of big-O notation, the equals sign does not mean equals. Trying to parse the equal sign literally leads to confusing and contradictory interpretations (which is why their explanation is confusion). You're misunderstanding the 3=5 example. Let f(n)=3n, let g(n)=5n. Using big-O notation, f(n)=O(n), g(n)=O(n). Were the equal sign behaving normally, then O(n) would be a single well-defined object, and one could use transitivity to conclude that 3n=5n. But of course this is false, because O(n) isn't a single function, nor really something that other functions can equal. It's a class of functions, not a function itself. It would be more appropriate to say that "f(n) belongs to O(n)," or more compactly, "f(n) ∈ O(n)." This is much closer to the real definition, and behaves appropriately when taken literally.
esrauch 14y ago
> This is not clear at all ! He is using 'type check' to point out the flaw. x = y means x and y are the same thing. If x is a function and y is an integer, then it can't possibly hold that x = y. Consider x = O(n). The implication would be that whatever type of thing O(n) is, x also is. This is trivially untrue. If x = y, and x is a function, then x(K) = y(K). It would be ridiculous to say that x(K) = O(n)(k). > Yes well, f(x) = f(y) does not implies x = y. I think people know this .. I don't understand why you are mentioning that. The issue is that x = f(z) and y = f(z), then x = y. You can't get two different values by applying the same function to the same value. Saying that f is O(n), the "is" is not an equality statement at all, "is" is some other function exactly as you mention that people understand. It is clearly some function that is non-transitive. In this case the relationship is most easily expressed using existing operators by having O(n) be a set of functions and the "is" in that sentence be the "exists-in" set operator, which is a case where the transitive property doesn't hold. Using the = symbol in that context is just bizarre when = is a otherwise always used to mean equality, which is function with special properties that don't apply here.

ambrop7 14y ago

Fun fact: there exist pairs of positive monotonic functions f(x) and g(x) such that neither f(x)=O(g(x)) nor g(x)=O(f(x)), i.e. the functions are not comparable asymptotically. Example: f(x)=gamma(floor(x)+1) (=floor(x)!) g(x)=gamma(floor(x-0.5)+1.5) There exists no such constant M>0 that f(x)<M*g(x) for x from some point on, and the converse. The two functions periodically cross each other in a way that neither is asymptotically bound by the other.

oskarkv 14y ago

The correct statement about lower bounds is this: "In the worst case, any comparison based sorting algorithm must make Ω(n log(n)) comparisons." You are making the same mistake that people that have Misconception 1 make. "The algorithm must make <a set of functions> comparisons." is a nonsensical statement.