Buscar
Estás en modo de exploración. debe iniciar sesión para usar MEMORY

   Inicia sesión para empezar

level: Level 1

Questions and Answers List

level questions: Level 1

QuestionAnswer
Describe halting problemIts the unsolvable problem of determining whether any program will eventually stop if given particular input OR without running solution
State the significance of haltings problemThe Halting problem demonstrates that there are some problems that cannot be solved by a computer
Whats the big O notation for constant timeO(C)
Whats the big O notation for lienar timeO(n)
Whats the big O notation for logarithmic time0(log_(n)) _ is a little 2
Whats the big O notation for polynomial time0(n^2)
Whats the big O notation for exponential timeO(2^n)
How to recognise a constant functionTimes independent of input
How to recognise a logarithmic functionHalves the number of items in each iteration
How to recognise a linear functionIn worst case scenario, it goes through each item once
How to recognise a polynomail functionLoop in side a loop
How to recognise a factorial or exponential functionCannot be solved in a useful amount of time
Define the term algorithmA 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 //