Facebook

complexity

Big Omega(Ω) Notation

Ω Notation provides the asymptotic lower bound on the function. A function needs to satisfy some conditions in order to be in Ω notation.Ω(g(n)) is the best case running time  of function g(n) within a constant factor. Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n… read more »

Big O Notation

  It gives rate of growth of step count function(f(n)) in terms of simple function(g(n)) and defines the asymptotic upper bound on function(Fig 1). To simplify the estimation for running time,constants and lower order terms are ignored. The function needs to satisfy following conditions in order to be in Big-O class.Given functions f(n) and g(n),we… read more »

Time and Space Complexity

Before defining the actual term complexity, let us discuss about few real life scenarios. Take an example of railway reservation counter, people go there to book their tickets. The time to book tickets will depend on  how many service windows are available, queue size and time taken by each representative. A person will either go… read more »

Sidebar