tag:blogger.com,1999:blog-17886948.post5856912107060978773..comments2024-10-01T14:38:34.841+05:30Comments on Hare Krishna: Algorithm Complexity - Interview Questionstnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-17886948.post-5639397330651685822011-05-04T23:18:53.437+05:302011-05-04T23:18:53.437+05:30Many people take the average case and say that the...Many people take the average case and say that the complexity of hashtable is O(1). In the same way, if we take the average no.of NP-complete problems and their average complexity, the complexity would be polynomial only. There are many NP-Complete problems, where 99% of the inputs can be solved by using polynomial algorithm. So, in average case NP=P. In this case, the average is much closer to the worst case than the Hashtable.tnsatishhttps://www.blogger.com/profile/11487701501347042727noreply@blogger.comtag:blogger.com,1999:blog-17886948.post-15721111458461742532011-05-04T21:38:29.790+05:302011-05-04T21:38:29.790+05:30"If you say, the complexity of Hashtable is O..."If you say, the complexity of Hashtable is O(1), then with the same logic, I would say, NP=P, and I am more accurate than you."<br /><br />I am really curious how you would do thatSVnoreply@blogger.com