Big-O for Eight Year Olds? [duplicate]

by

One way of thinking about it is this:

O(N^2) means for every element, you’re doing something with every other element, such as comparing them. Bubble sort is an example of this.

O(N log N) means for every element, you’re doing something that only needs to look at log N of the elements. This is usually because you know something about the elements that let you make an efficient choice. Most efficient sorts are an example of this, such as merge sort.

O(N!) means to do something for all possible permutations of the N elements. Traveling salesman is an example of this, where there are N! ways to visit the nodes, and the brute force solution is to look at the total cost of every possible permutation to find the optimal one.

More Related Contents:

  1. time complexity of recursion function
  2. What is a plain English explanation of “Big O” notation?
  3. What does O(log n) mean exactly?
  4. Constant Amortized Time
  5. What exactly does big Ө notation represent?
  6. Can hash tables really be O(1)?
  7. Is log(n!) = Θ(n·log(n))?
  8. Difference between Big-O and Little-O Notation
  9. How can building a heap be O(n) time complexity?
  10. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  11. Which algorithm is faster O(N) or O(2N)?
  12. Time complexity of Euclid’s Algorithm
  13. What is pseudopolynomial time? How does it differ from polynomial time?
  14. Quick sort Worst case
  15. What is Constant Amortized Time?
  16. Computing set intersection in linear time?
  17. What would cause an algorithm to have O(log n) complexity?
  18. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  19. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  20. How do I check if a directed graph is acyclic?
  21. Quicksort superiority over Heap Sort
  22. Why do we ignore co-efficients in Big O notation?
  23. Big O when adding together different routines
  24. Time Complexity of two for loops [duplicate]
  25. Print the biggest K elements in a given heap in O(K*log(K))?
  26. Calculating phi(k) for 1
  27. The intersection of all combinations of n sets
  28. Prove that binary heap build max comparsion is (2N-2)
  29. Difference between Big-Theta and Big O notation in simple language
  30. Why is bubble sort O(n^2)?

Leave a Comment