Omega notation, Data Structure & Algorithms

The ?-Notation (Lower Bound)

This notation provides a lower bound for a function to within a constant factor. We write f(n) = ?(g(n)), if there are positive constants n0 and c such that to the right of n0, value of f(n) always lies on or above cg(n). Figure illustrates the plot of f(n) = ?(g(n)).

369_Omega Notation.png

Figure: Plot of  f(n) = ?(g(n))

Mathematically specking, for a given function g(n), we might define ?(g(n)) as the set of functions.

?(g(n)) = { f(n) : there presents constant c & n0 ≥ 0 such that 0 ≤  cg(n) ≤ f(n) for every n ≥ n0 }.

As ? notation define lower bound, it is utilized to bind the best case running time of an algorithm.

Posted Date: 4/4/2013 5:45:39 AM | Location : United States







Related Discussions:- Omega notation, Assignment Help, Ask Question on Omega notation, Get Answer, Expert's Help, Omega notation Discussions

Write discussion on Omega notation
Your posts are moderated
Related Questions
Write an algorithm in form of a flowchart that takes temperatures input over a 100 day period (once per day) and outputs the number of days when temperature was below 20C and numbe

What is binary search?   Binary search is most useful when list is sorted. In binary search, element present in middle of the list is determined. If key (the number to search)

explain collision resloving techniques in hasing

By changing the NULL lines in a binary tree to the special links called threads, it is possible to execute traversal, insertion and deletion without using either a stack or recursi

Time Complexity, Big O notation The amount of time needed by an algorithm to run to its completion is referred as time complexity. The asymptotic running time of an algorithm i

Explain the term totalling To add up a series numbers the subsequent type of statement must be used: Total = total + number  This literally means (new) total = (old) t

Q. Calculate that how many key comparisons and assignments an insertion sort makes in its worst case?        Ans: The worst case performance occurs in insertion


Graphs are data structures which consist of a set of vertices & a set of edges which connect the vertices. A graph where the edges are directed is called directed graph. Or else, i

basic calculation for algorith.