Do you think there is a solution better than O(n^2)?

  • -1
    If your answer is:
        yes ->  show a solution 
        no  ->  prove it or state why you think it should be that way

  • -13

    I have an O(n) solution. think about what n is.

  • 3

    No, it definitely cannot be better than O(n^2). To see this, consider a rectangle that contains all 1's. You definitely have to ckeck each and every square to find the maximum rectangle!

  • 0

    That's stupid. It's like saying I can do bubble sort in O(n) by defining n to be the length of the list squared.

  • 0

    No, one cannot define N arbitrarily, one cannot "define n to be length of the list squared" as you said.

    N is defined as the size of the input data. period.

    if there are K numbers as input to be sorted, they are probably stores in some fixed format meaning that each number in the input represented by fixed size (1,2,4, or 8 bytes or maybe more, doesn't matter, lets call this x bytes for each number) therefore size of input is exactly k*x bytes. that is our number N.

    in this problem say if there are kk numbers, input size is kk*x bytes. that is our number N. rock solid definition as that.

  • 0

    What? N is defined by whatever you want. There is no rule that it has to be the input size. Even if it was, are you using a word-RAM model? The definition of N is not so "sock solid."

    In problems like this with a matrix, N is often the max of the width and height of the matrix. Again, it does not have to be. Think of other types of problems, like graphs. Is N the size of the graph? How do you measure the size of a graph? The number of bits or words to represent it? Convention says N is the number of vertices.

    PS: The number you call x is not a constant. x is bound by the lg2 of the numbers you can represent.

  • 0

    you say "N is defined by whatever you want."

    ok then in this problem I define N as the 54th power of the number of rows in the matrix. that is what I want :)

  • 0

    Actually there are more things I want.

    in "Boolean satisfiability problem" (which is NP-complete) I "want" to define N to be 2 to the power 'number of variables in the given boolean formula'. Then I found an algorithm (brute force) that is O(N) oh wow. I just solved an NP-Complete problem in polynomial time which means I solved P=NP problem. Can I get 3 nobel prizes among many other prizes + millions of dollars please? Moreover a place in the history by being one of the most known discoverers in the entire human history is what I deserve by this extraordinary achievement (ehem, wanting something)

    I liked this customer service

  • 0

    N is a variable. That is why it can be anything, not necessarily the input size. But what you choose N to be is not so important that it is accepted by the definition of SAT problem. NP-complete problem terminology usually says something more like "... deterministic exponential time in the input size" not "... in N."

    A problem can be stated as something like "Given an NxN matrix, do..." here N is the length of a side of the square matrix, not the input size. Remember, N is just a variable.

    Your ridiculous examples are some of the reason why I said "that is stupid" in my original reply. You are obviously comparing your "O(N)" solution to others' "O(N^2)" solutions and pretending your N is the "real" N.

    In theory, the real input size is not even N where N is the number of integers. The real input size is N*[lgN] bits where N is the number of integers because the word size matters. If you say word size is 4, or 8, or whatever then you are limiting the value of N, and you can't do that in asymptotic analysis. The only reason you get away with that most of the time is because you are analyzing a computer program, and not an algorithm. The N that I would use for a problem like this is the max of width or height of the matrix, and analyses it using a standard word-RAM model. My analysis and your analysis are not comparable.

    You are solving problems on this site and doing well. You probably are very good at the practical side of things. I am curious if you have formal education in the field, or do it as a hobby? If the latter, I recommend you study theory of computation and complexity theory.

  • 0

    It is more clear what you say with you last message. because the way " N is defined by whatever you want." sounds like results in a conclusion that we cannot do science.

    declaring an algorithm O(N^2) suggests that it is quadratic. But actually the algorithms presented for this problem here are all linear. do you agree?

    "In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input"
    Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.

    and we assume some bounded-value representation of numbers. why would this take us out of theory? we need to also make some cost model assumption as well. for instance does a comparison take logarithmic cost or constant cost? we have to make an assumption.

    you say 'real input size of N numbers is N*lgN'. I agree that it is the measure of information content in terms of Shannon's entropy if we don't put a bound on values of numbers. In that case, I would love to hear your "asymptotic analysis" of quicksort algorithm

    P.S.: I thought you are hobbyist without formal education too. I have >10 years of formal computer science education including PhD but I don't want to go into "I am better than you" toned discussion, I want to have fruitful discussion

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.