gatebook_dsa

Question

explain!

Comments

@anonymous.

Its asking for the time complexity in worst case using the best algorithm. Its not time complexity using the worst algorithm :)

For example, I can transform Dijkstras algorithm into other algo such that it takes polynimial/exponential time for running. THat doesnt mean worst case time complexity is polynomial/exponential.

---

Hi Sushant, i'm entirely new to gate questions. Was aware this algorithm is the worst kind. However, are we suppose to have wild assumptions ? I mean, question doesn't specify, if it meant for an algorithm of smaller input size or larger input size since there are algorithms that does well for smaller sizes.

So here which algorithm are we suppose to assume ? Some are saying it should be sorted, while others say it need not. I may be missing something.  

So, i strongly believe that, questions having soo much assumptions which would vary with person to person, isn't a good fit. Am i right ?

---

@altaf.

Make minimum assumptions. Assumption is what you feel :). It may not be the best.

Make assumptions only to the point of deriving the answer or mandatory for deriving the answer. If assumption is giving you best answer, hold it.

You should think of the best algorithm because no one will ask you whats the worst algorithm :)

---

why are people posting questions as blogs ?

---

Hashing solves it in O(n) time ..and if hashing is not prmitted then sorting by nlogn time

ps: post queries as a question..not as a blog

Answer 1

explain!

Answer 2

@anonymous.

Its asking for the time complexity in worst case using the best algorithm. Its not time complexity using the worst algorithm :)

For example, I can transform Dijkstras algorithm into other algo such that it takes polynimial/exponential time for running. THat doesnt mean worst case time complexity is polynomial/exponential.

Answer 3

Hi Sushant, i'm entirely new to gate questions. Was aware this algorithm is the worst kind. However, are we suppose to have wild assumptions ? I mean, question doesn't specify, if it meant for an algorithm of smaller input size or larger input size since there are algorithms that does well for smaller sizes.

So here which algorithm are we suppose to assume ? Some are saying it should be sorted, while others say it need not. I may be missing something.  

So, i strongly believe that, questions having soo much assumptions which would vary with person to person, isn't a good fit. Am i right ?

Answer 4

@altaf.

Make minimum assumptions. Assumption is what you feel :). It may not be the best.

Make assumptions only to the point of deriving the answer or mandatory for deriving the answer. If assumption is giving you best answer, hold it.

You should think of the best algorithm because no one will ask you whats the worst algorithm :)

Answer 5

why are people posting questions as blogs ?

Answer 6

Hashing solves it in O(n) time ..and if hashing is not prmitted then sorting by nlogn time

ps: post queries as a question..not as a blog