level: Level 1
Questions and Answers List
level questions: Level 1
| Question | Answer |
|---|---|
| Describe halting problem | Its the unsolvable problem of determining whether any program will eventually stop if given particular input OR without running solution |
| State the significance of haltings problem | The Halting problem demonstrates that there are some problems that cannot be solved by a computer |
| Whats the big O notation for constant time | O(C) |
| Whats the big O notation for lienar time | O(n) |
| Whats the big O notation for logarithmic time | 0(log_(n)) _ is a little 2 |
| Whats the big O notation for polynomial time | 0(n^2) |
| Whats the big O notation for exponential time | O(2^n) |
| How to recognise a constant function | Times independent of input |
| How to recognise a logarithmic function | Halves the number of items in each iteration |
| How to recognise a linear function | In worst case scenario, it goes through each item once |
| How to recognise a polynomail function | Loop in side a loop |
| How to recognise a factorial or exponential function | Cannot be solved in a useful amount of time |
| Define the term algorithm | A sequence of steps that can be followed to complete a task and that always terminates |
| What does it mean for a problem to be described as intractable? | The problem can be solved; But not in polynomial time // |