Big O Notation Flashcards
what is n
the size of the input
what two things are considered whenh analysing an algorithm
- time complexity
- space complexity
what is time complexity
the amount of time it takes to run an algorithm
what three cases may be found when analysing the time cpmplexity of an algorithm
- best case
- average case
- worst case
what is meant by best case
the complexity of solving the problem with the best input
what is meant by average case
the average comlexity of solving a problem
what is meant by worst case
the complexity of solving a problem for the worst size input
what is the time complexity of a linear search alogirthm
O(n)
what is the time complexity of a binary search alogirthm
O(log n)
what is the time complexity of a binary tree search alogirthm
O(log n)
what is the time complexity of a bubble sort alogirthm
O(n^2)
what is the time complexity of a merge sort alogirthm
O(n log n)
what is meant by an intractable problem
a problem that cannot be solved in a reasonable amount of time but can be solved
what approach might a programmer take if asked to “solve” an intractable problemn
use hiuristic methods whic make estimates based on experience
explauin why the bubble sort has a time complexity of O(n^2)
there is a loop within a loop
explain why a linear search has a time complexity of O(n)
the number of iterations is dependant on how many items are in the array
