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.
Takk for tilbakemeldingene dine!
Spør AI
Spør AI
Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår
Still meg spørsmål om dette emnet
Oppsummer dette kapittelet
Vis eksempler fra virkeligheten
Awesome!
Completion rate improved to 4.35Asymptotic Notations 2/2
Sveip for å vise menyen
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.
Takk for tilbakemeldingene dine!
