Thread: complexity

Try here.

Of course! Complexity in computer science refers to the difficulty of an exam question or number of exam questions. Each question represents an equal part of the work such as a multiple choice, fill in the blank or a true or false answer. We assume that these will be answered in constant time, or, in Big-Oh notation, O(1).

If you wanted to know the complexity of the whole exam, you could measure it in terms of the amount of work you have to do as the size grows. Commonly you will have to answer questions in linear time, or O(n). Sometimes you'll discover a question you answered wrong while checking your work, and need to repeat the steps. This usually ends up with a measurement like O(n^2) or if you're very unlucky O(n^3).

Other people study and are able to answer the questions in subsets. They occasionally go back to the start of the test once they've finished a section of answers (like T/F). This means that the exam taking time is at most the height of the whole heap (or "recursion tree" as the technical term). These students regularly perform at O(n lg n).

It is possible to go faster than O(n lg n) for test taking, but if you do, then you are a machine who is capable of answering questions in batches and having those answers be correct.

Originally Posted by whiteflags

Of course! Complexity in computer science refers to the difficulty of an exam question or number of exam questions. Each question represents an equal part of the work such as a multiple choice, fill in the blank or a true or false answer. We assume that these will be answered in constant time, or, in Big-Oh notation, O(1).

If you wanted to know the complexity of the whole exam, you could measure it in terms of the amount of work you have to do as the size grows. Commonly you will have to answer questions in linear time, or O(n). Sometimes you'll discover a question you answered wrong while checking your work, and need to repeat the steps. This usually ends up with a measurement like O(n^2) or if you're very unlucky O(n^3).

Other people study and are able to answer the questions in subsets. They occasionally go back to the start of the test once they've finished a section of answers (like T/F). This means that the exam taking time is at most the height of the whole heap (or "recursion tree" as the technical term). These students regularly perform at O(n lg n).

It is possible to go faster than O(n lg n) for test taking, but if you do, then you are a machine who is capable of answering questions in batches and having those answers be correct.

wow, that was a really good explanation

Wouldn't your textbook talk about it?