Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
DavH4462.3BigO
H446 2.3 Complexity of Algorithms and Big O
| Question | Answer |
|---|---|
| Explain what is meant by big O time complexity, | How the time scales as data size increases |
| What is meant by a big O time complexity of O(n) | O(n) is linear complexity. Increases at the same rate as the number of data items increases. |
| State the purpose of Big O notation | Evaluate the complexity of an algorithm. Show how the time/memory increase/scale as the data size increases. Evaluate the worst-case scenario for an algorithm. |
| State the big O best-case complexity for a linear search | O(1) constant |
| State the big O average-case complexity for a linear search | O(n) linear |
| State the big O worst-case complexity for a linear search | O(n) linear |
| What does best time O(n) mean? | Best time grows at the same rate as the number of elements This is the case for many sorting algorithms when the data is already in order |
| What does Average and worst time O(n2) (n squared) mean | Polynomial / Quadratic Worst and average time is proportional to the square (polynomial) of the number of elements Worst case is when the data is initially in the reverse order |
| What does worst space O(1) mean | Constant Will always take the same amount of memory (in addition to the list itself). |
| What is the best case time complexity for bubble sort | O(n) linear. This is the case if the list is already sorted. |
| What is the best case time complexity for insertion sort | O(n) linear. This is the case if the list is already sorted. |
Created by:
Davenant Computer Science
Popular Computers sets