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 // |