1

Claim: I can traverse an $n \times n$ matrix in $O(n)$.

"Proof": Clearly, this is true for $n=1$. Now suppose this is true for $n-1$. Then given an $n \times n$ matrix, traverse the upper left $(n-1)\times(n-1)$ matrix in $O(n-1)$ time, and then the remaining row and column in $O(2n)$ time. This gives $O(n-1) + O(2n) = O(n)$ time.

What's wrong with this?

user48372
  • 35
  • 3
  • 1
    $n=1$ is not the true base case! – Ehsan M. Kermani Sep 05 '14 at 16:28
  • 1
    That is not true for $n=1$ because that isn't even a condition on $n$, the formula you want to prove in not generalized in the variable $n$.

    Think about the affirmation that you are proving for n=1; you state that the time to transverse a matrix is bounded by c n for some real c as n-> infinity when n=1?

     – PenasRaul Sep 05 '14 at 16:28
  • 4
    The idea of "big O" notation doesn't make sense without a parameter to vary. If you have a matrix of fixed size, what does it mean to "grow with $n$" anymore? Try proving you can traverse a list in constant time with a similar method, if that makes the idea more clear. – Henry Swanson Sep 05 '14 at 16:30

1 Answers1

2

You take a turn for the worst at the first statement.

It just so happens that $n=1$ is the only positive integer for which $n^2=n$. Now that you've seeded our thinking with plausible deniability -- it sure looks like it's $O(n)$ for $n=1$ -- you then run with it in the rest of the proof.

John
  • 26,319
  • 3
    It doesn't event make sense to speak of $O(n)$ when $n = 1$, since the big-O notation expresses the asymptotic behaviour when $n \rightarrow \infty$. – lmsteffan Sep 05 '14 at 16:33
  • Of course! I didn't say it made sense. But that's where the "old switcheroo" was made that derails the proof. – John Sep 05 '14 at 16:34
  • To add: the switcharoo is more apparent if you look at the case of $n=2$ as the base case. We can claim that we traverse this is $O(2n)$. Clearly, that's the slight of hand. – BeaumontTaz Sep 05 '14 at 16:36