Big O Notation

Big O Notation.

What is Big O?. Is a mathematical function used in computer science to describe an algorithm’s complexity. It is usually a measure of the runtime required for an algorithm’s execution. But, instead of telling you how fast or slow an algorithm’s runtime is, it tells you how an algorithm’s performance changes with the size of the input (size n).define O(g(n)) as a set of functions and a function f(n) can be a member of this set if it satisfies the following conditions: 0 ≤ f(n) ≤ cg(n) ≤ f(n) ≤ cg(n).

What is space complexity and time complexity?. The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Similarly, the Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input. Here’s some common complexities you’ll find for algorithms: Quadratic time: O(n^2)​ Linear time: O(n) Logarithmic time: O(n log n).

Means that for each increment of the input size, the speed of the algorithm will double. An example of this, is an algorithm that looks for duplicates in an array. Note the nested loop that increase the execution time. def duplicates?(array1) array1.each_with_index do |item1, index1| array1.each_with_index do |item2, index2| next if index1 == index2 return true if item1 == item2 end end false end.

Means that the execution time of an algorithm will grow linearly depending on the input size. def contains?(array, value) array.each do |item| return true if item == value end false end.

Is harder to explain. If I was to show you a graph, we would have a quick growth at the beginning, that tends to get slower in time if you increase the size of the input.A good example is the Binary Search Algorithm. def binary_search(array, value, from=0, to=nil) to = array.count - 1 unless to mid = (from + to) / 2 if value < array[mid] return binary_search(array, value, from, mid - 1) elsif value > array[mid] return binary_search(array, value, mid + 1, to) else return mid end end.

Conclusion. Knowing the runtimes of algorithms and how to improve them is why Big O Notation exists. Developing more efficient algorithms leads to faster runtimes and less code..