what is order of complexity in Big O notation?

Question

Question

Hi I am trying to understand what order of complexity in terms of Big O notation is. I have read many articles and am yet to find anything explaining exactly 'order of complexity', even on the useful descriptions of Big O on here.

What I already understand about big O

The part which I already understand. about Big O notation is that we are measuring the time and space complexity of an algorithm in terms of the growth of input size n. I also understand that certain sorting methods have best, worst and average scenarios for Big O such as O(n) ,O(n^2) etc and the n is input size (number of elements to be sorted).

Any simple definitions or examples would be greatly appreciated thanks.

Answer 1

Big-O analysis is a form of runtime analysis that measures the efficiency of an algorithm in terms of the time it takes for the algorithm to run as a function of the input size. It’s not a formal bench- mark, just a simple way to classify algorithms by relative efficiency when dealing with very large input sizes.

Update: The fastest-possible running time for any runtime analysis is O(1), commonly referred to as constant running time.An algorithm with constant running time always takes the same amount of time to execute, regardless of the input size.This is the ideal run time for an algorithm, but it’s rarely achievable. The performance of most algorithms depends on n, the size of the input.The algorithms can be classified as follows from best-to-worse performance:

O(log n) — An algorithm is said to be logarithmic if its running time increases logarithmically in proportion to the input size.

O(n) — A linear algorithm’s running time increases in direct proportion to the input size.

O(n log n) — A superlinear algorithm is midway between a linear algorithm and a polynomial algorithm.

O(n^c) — A polynomial algorithm grows quickly based on the size of the input.

O(c^n) — An exponential algorithm grows even faster than a polynomial algorithm.

O(n!) — A factorial algorithm grows the fastest and becomes quickly unusable for even small values of n.

The run times of different orders of algorithms separate rapidly as n gets larger.Consider the run time for each of these algorithm classes with

   n = 10:
   log 10 = 1
   10 = 10
   10 log 10 = 10
   10^2 = 100
   2^10= 1,024
   10! = 3,628,800
   Now double it to n = 20:
   log 20 = 1.30
   20 = 20
   20 log 20= 26.02 
   20^2 = 400
   2^20 = 1,048,576 
   20! = 2.43×1018

Finding an algorithm that works in superlinear time or better can make a huge difference in how well an application performs.