algorithms « Lotusland of Mathematical Dreams

Random Question (1) October 25, 2009

Posted by jagadeeshbp in Uncategorized.
Tags: algorithms, computational complexity
add a comment

Are there transformers for P problems, like SAT in NP-Complete? For all problems X in P, there’s a single problem Y s.t. Y is polynomial time reducible to X?

Revisiting Algorithm Analysis April 24, 2009

Posted by jagadeeshbp in Uncategorized.
Tags: algorithms, Big O, computer science, theory
add a comment

Yet again, another subject that I dreaded due to the incomprehensible and intangible approach in which the subject was taught. One fundamental question I had was, knowing the definition of Big O notation, what does $O(f(n))$ really mean?

Let me try to put them in my perspective. Think that I am planning to go and buy a new shirt and I do not know what its exact cost is. But to make sure that I have enough money to buy one, I kind of predict, it would cost at the maximum of say a $1000 (I would love it as a gift, better). That is sort of the upper bound. I know that the cost will not go beyond that; even in the worst case.

Big O notation is similar to that. It defines an upperbound to the complexity of the function. Consider the case of sorting $n$ elements, the time taken (considering time complexity, we can worry about space complexity some other time) is given by the function $f(n) = n^3+n^2+1$ . By the definition of Big O, the upper bound is $O(f(n)) = n^3$ . We can get this by removing all constants, and lower order terms, leaving us with just $n^3$ .

By definition, $f(n) = O(g(n))$ means that for some constants $n_0>0$ and $C>0$ , $0 leq f(n) leq C.g(n)$ , $forall n geq n_0$

Let us try to interpret this. $0leq f(n)$ part means that we are considering the positive values of $f(n)$ .

Following shows how the graphs of the functions $f(x) = x^3+x^2+14$ , $f(x) = x^3$ and $f(x) = 2.x^3$ looks like.

It is can be seen that $f(x) = 2.x^3$ is above $f(n) = x^3+x^2+1 forall x ge 0$ .