Big o notation, Data Structure & Algorithms

This notation gives an upper bound for a function to within a constant factor. Given Figure illustrates the plot of f(n) = O(g(n)) depend on big O notation. We write f(n) = O(g(n)) if there are positive constants n0 & c such that to the right of n0, the value of f(n) always lies on or below cg(n).

2388_The o-Notation.png

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

Mathematically specking, for a given function g(n), we specified a set of functions through O(g(n)) by the following notation:

O(g(n)) = {f(n) :  There exists a positive constant c and n0 such that 0 ≤  f(n) ≤ cg(n)

for all n ≥ n0 }

Obviously, we employ O-notation to describe the upper bound onto a function using a constant factor c.

We can view from the earlier definition of Θ that Θ is a tighter notation in comparison of big-O notation. f(n) = an + c is O(n) is also O(n2), but O (n) is asymptotically tight while O(n2) is notation.

While in terms of Θ notation, the above function f(n) is Θ (n). Because of the reason big-O notation is upper bound of function, it is frequently used to define the worst case running time of algorithms.

Posted Date: 4/4/2013 5:44:26 AM | Location : United States

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

Write discussion on Big o notation
Your posts are moderated
Related Questions
Write an algorithm for multiplication of two sparse matrices using Linked Lists.

I need help writing a pseudocode for my assignment can anyone help?

Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)

Give example of assertion and abstract data type For illustration, consider Natural ADT whose carrier set is the set of non-negative integers and whose operations are the usual

AVL tree An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most 1 and in which the left and right subtrees are again

Q. Write down the recursive function to count the number of the nodes in the binary tree.    A n s . R ecursive Function to count no. of Nodes in Binary Tree is writt

Explain Space Complexity Space Complexity :- The space complexity of an algorithm is the amount of memory it requires to run to completion. Some of the reasons to study space

You will write functions for both addition and subtraction of two numbers encoded in your data structure. These functions should not be hard to write. Remember how you add and subt

Q. Sort the sequence written below of keys using merge sort. 66, 77, 11, 88, 99, 22, 33, 44, 55                                                                      Ans:

ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in