Polynomial time and exponential time

by

Below are some common Big-O functions while analyzing algorithms.

  • O(1) – Constant time
  • O(log(n)) – Logarithmic time
  • O((log(n))c) – Polylogarithmic time
  • O(n) – Linear time
  • O(n log(n)) – Linearithmic time
  • O(n2) – Quadratic time
  • O(nc) – Polynomial time
  • O(cn) – Exponential time
  • O(n!) – Factorial time

(n = size of input, c = some constant)

Here is the model graph representing Big-O complexity of some functions

graph model

graph credits http://bigocheatsheet.com/

More Related Contents:

  1. How do I search for a number in a 2d array sorted left to right and top to bottom?
  2. Quicksort: Choosing the pivot
  3. Breadth First Vs Depth First
  4. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  5. Time complexity of Euclid’s Algorithm
  6. Quick sort Worst case
  7. Is there an efficient algorithm to generate a 2D concave hull?
  8. How to round floats to integers while preserving their sum?
  9. Modulus power of big numbers
  10. Fast algorithm implementation to sort very small list
  11. Compute social distance between two users
  12. Efficient algorithm for ordering different types of objects
  13. How to find two most distant points?
  14. Algorithm to find two repeated numbers in an array, without sorting
  15. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  16. How to implement depth first search for graph with a non-recursive approach
  17. Why is the time complexity of both DFS and BFS O( V + E )
  18. How to split a string into words. Ex: “stringintowords” -> “String Into Words”?
  19. Mesh generation from points with x, y and z coordinates
  20. How do you find a point at a given perpendicular distance from a line?
  21. How to find distance from the latitude and longitude of two locations?
  22. Myers diff algorithm vs Hunt–McIlroy algorithm
  23. Given Prime Number N, Compute the Next Prime?
  24. Randomly choosing from a list with weighted probabilities
  25. Planar Graph Layouts
  26. Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location
  27. How do ASCII art image conversion algorithms work? [closed]
  28. Reason for the number 5381 in the DJB hash function?
  29. What is the best algorithm for finding the closest color in an array to another color? [closed]
  30. Quadratic algorithm for 4-SUM

Leave a Comment