Tuesday, 2 May 2017

Time Complexity of Data Structure Operations



Big-O, Little-O, Theta, Omega

Big-O, Little-o, Omega, and Theta are formal notational methods for stating the growth of resource needs (efficiency and storage) of an algorithm. There are four basic notations used when describing resource needs. These are: O(f(n)), o(f(n)), Ω(f(n))\Omega(f(n))Ω(f(n)), and Θ(f(n))\Theta(f(n))Θ(f(n)). (Pronounced, Big-O, Little-O, Omega and Theta respectively)

  • Big-O -- asymptotic upper bound (inclusive)
  • little-o -- asymptotic upper bound (exclusive)
  • Theta -- asymptotic tight bound (Big-O and Big-Omega)
  • Big-Omega -- asymptotic lower bound (inclusive)
Best/worst/average case runtimes are specific values (can be asymptotic) that describe the shortest possible runtime, longest possible runtime, and expected runtime. 




Common Data Structure Operations
Data Structure
Time Complexity
Space Complexity

Average
Worst
Worst

Access
Search
Insertion
Deletion
Access
Search
Insertion
Deletion

Θ(1)
Θ(n)
Θ(n)
Θ(n)
O(1)
O(n)
O(n)
O(n)
O(n)
Θ(n)
Θ(n)
Θ(1)
Θ(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Θ(n)
Θ(n)
Θ(1)
Θ(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Θ(n)
Θ(n)
Θ(1)
Θ(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Θ(n)
Θ(n)
Θ(1)
Θ(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(n)
O(n)
O(n)
O(n)
O(n log(n))
N/A
Θ(1)
Θ(1)
Θ(1)
N/A
O(n)
O(n)
O(n)
O(n)
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(n)
O(n)
O(n)
O(n)
O(n)
N/A
Θ(log(n))
Θ(log(n))
Θ(log(n))
N/A
O(n)
O(n)
O(n)
O(n)
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
N/A
Θ(log(n))
Θ(log(n))
Θ(log(n))
N/A
O(log(n))
O(log(n))
O(log(n))
O(n)
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Θ(log(n))
Θ(log(n))
Θ(log(n))
Θ(log(n))
O(n)
O(n)
O(n)
O(n)
O(n)


Array Sorting Algorithms
Algorithm
Time Complexity
Space Complexity

Best
Average
Worst
Worst
Ω(n log(n))
Θ(n log(n))
O(n^2)
O(log(n))
Ω(n log(n))
Θ(n log(n))
O(n log(n))
O(n)
Ω(n)
Θ(n log(n))
O(n log(n))
O(n)
Ω(n log(n))
Θ(n log(n))
O(n log(n))
O(1)
Ω(n)
Θ(n^2)
O(n^2)
O(1)
Ω(n)
Θ(n^2)
O(n^2)
O(1)
Ω(n^2)
Θ(n^2)
O(n^2)
O(1)
Ω(n log(n))
Θ(n log(n))
O(n^2)
O(n)
Ω(n log(n))
Θ(n(log(n))^2)
O(n(log(n))^2)
O(1)
Ω(n+k)
Θ(n+k)
O(n^2)
O(n)
Ω(nk)
Θ(nk)
O(nk)
O(n+k)
Ω(n+k)
Θ(n+k)
O(n+k)
O(k)
Ω(n)
Θ(n log(n))
O(n log(n))
O(n)


No comments:

Post a Comment