I was given this task:
Algorithm M(n)
if n=1 then
Execute Task A; // Requires Theta(1) operations
else
Execute Task B; //Requires 2n operations
end if
What does "Requires Theta(1) operations" mean?
What does Theta(1) operations mean?
Viewed 593
1 Answers
What does "Requires Theta(1) operations" mean?
It means, that something requires constant amount of operations in the average-case scenario.
What is Big Theta?
Big Theta notation (Θ) is an Asymptotic Notation, which denotes the Average Case Complexity of an algorithm.
Popular Asymptotic Notation letters are:
Ο(Big-O) – used to express worst case complexity scenario.Ω(Big Omega) – used to express best case complexity scenario.θ(Big Theta) – used to express average case complexity scenario.
Few examples:
- Ω(1) - means, that best-case scenario runs in constant time (we use
1to denote constant running-time, that does not grow as the input grows); - θ(n) - means, that average-case scenario runs in n time (running-time is said to be growing linearly to the growth of the input size);
- O(n2) - means, that worst-case scenario runs in n2 time (running-time is said to be growing quadratically to the growth of the input size).
Additionally, have a look at this.
Related