0

On Formal Reasoning

As I am going through Introduction to Algorithms course from MIT, just past the first lecture, we can see the importance of formally proving an algorithm correct. If an algorithm is intuitively incorrect at first, then the need for formal reasoning becomes even more important.

Coming to the 2-d peak finding algorithm, here is a semi-formal reasoning:

  • When we find a global maximum in a column and shift to either left (right), it is because this global maximum is less than the left (right) element. So, if there is a new global maximum in this column, then it is definitely more than all the elements in the previous column because it is more than the left (element) itself. So, the algorithm works.
  • Will the same argument apply if we find a 1-D peak in a column instead of a global maximum? Does not look to me like so…
0

Theta, O and Omega…

The first recitation lecture of Introduction to algorithms gives a different introduction to the asymptotic complexity.

  • Theta (n) is when you can get a function g(x) and constants m and n such that our candidate complexity function f(x) is between m.g(x) and n.g(x) – i.e Theta(n) can be said if we can find a function such that it can serve as both tight upper and lower bounds of the candidate function
  • When such a function is not possible (lets say we have a sin(x) in the function, per lecture), then we can only find a function g(x) such that f(x) is not more than m.g(x) (there is no “not less than” clause) here. When this is the case, we have O(n)
  • When there are both lower bounds and upper bounds for the candidate function f(x), but the lower and upper bounds are not with in a constant factor away, then Theta cannot be used. We can use Omega(lb(x)) or O(ub(x)) – where lb(x) and ub(x) are the lower and the upper bound functions in x respectively.