Asymptotic Notations 2/2
How to pronounciate the evaluation?
Speaking about the first case candies problem, we may say: In the worst case, the complexity will be O(n) (n - the number of candies).
Speaking about the second case candies problem, we may say: In the worst case, the complexity will be O(n log n) (because it is a Binary Search algorithm; we will talk about that later).
There are a lot of evaluations that show the limits of time complexity.
O-little (o(n)), for example, is used to describe an upper bound that cannot be tight. Omega notation (Ω(n)) represents the lower bound of the running time of an algorithm.
| Operator | The name |
|---|---|
= | θ(n) |
≤ | O(n) |
< | o(n) |
≥ | Ω(n) |
> | ω(n) |
By exploring the picture, we can decide which time complexity is the best for the algorithm and which is the worst.
As we decided earlier, sometimes we have a choice to buy a more expensive washer machine (O(n)) or cheaper (O(n log n), for example). There are many cases where we have only one possible way to cope with the problem, so we need to buy that only one washing machine.
Best, worst, average
Mostly used. Best case (Big-O or O(n) )is the function which performs the minimum number of steps on input data of n elements.
Worst case (Omega or Ω(n)) is the function which performs the maximum number of steps on input data of size n.
Average case (Theta or θ(n)) is the function which performs an average number of steps on input data of n elements.
Bedankt voor je feedback!
Vraag AI
Vraag AI
Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.
Stel mij vragen over dit onderwerp
Vat dit hoofdstuk samen
Toon voorbeelden uit de praktijk
Awesome!
Completion rate improved to 4.35Asymptotic Notations 2/2
Veeg om het menu te tonen
How to pronounciate the evaluation?
Speaking about the first case candies problem, we may say: In the worst case, the complexity will be O(n) (n - the number of candies).
Speaking about the second case candies problem, we may say: In the worst case, the complexity will be O(n log n) (because it is a Binary Search algorithm; we will talk about that later).
There are a lot of evaluations that show the limits of time complexity.
O-little (o(n)), for example, is used to describe an upper bound that cannot be tight. Omega notation (Ω(n)) represents the lower bound of the running time of an algorithm.
| Operator | The name |
|---|---|
= | θ(n) |
≤ | O(n) |
< | o(n) |
≥ | Ω(n) |
> | ω(n) |
By exploring the picture, we can decide which time complexity is the best for the algorithm and which is the worst.
As we decided earlier, sometimes we have a choice to buy a more expensive washer machine (O(n)) or cheaper (O(n log n), for example). There are many cases where we have only one possible way to cope with the problem, so we need to buy that only one washing machine.
Best, worst, average
Mostly used. Best case (Big-O or O(n) )is the function which performs the minimum number of steps on input data of n elements.
Worst case (Omega or Ω(n)) is the function which performs the maximum number of steps on input data of size n.
Average case (Theta or θ(n)) is the function which performs an average number of steps on input data of n elements.
Bedankt voor je feedback!
