Big o notation, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Big o notation

Sorting algorithm is best if the list is already sorted, Which sorting algo...

Which sorting algorithm is best if the list is already sorted? Why? Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order

Doubly linked lists-implementation, In any singly linked list, each of the ...

In any singly linked list, each of the elements contains a pointer to the next element. We have illustrated this before. In single linked list, traversing is probable only in one d

Time complexity, Run time complexity of an algorithm is depend on

Run time complexity of an algorithm is depend on

Kruskals algorithm, Krushkal's algorithm uses the concept of forest of tree...

Krushkal's algorithm uses the concept of forest of trees. At first the forest contains n single node trees (and no edges). At each of the step, we add on one (the cheapest one) edg

Travelling salesman problem, Example 3: Travelling Salesman problem G...

Example 3: Travelling Salesman problem Given: n associated cities and distances among them Find: tour of minimum length that visits all of city. Solutions: How several

Abstract data type-tree, Definition: A set of data values & related operati...

Definition: A set of data values & related operations that are accurately specified independent of any particular implementation. As the data values and operations are described

Er diagram, Ask queConsider the following functional dependencies: Applican...

Ask queConsider the following functional dependencies: Applicant_ID -> Applicant_Name Applicant_ID -> Applicant_Address Position_ID -> Positoin_Title Position_ID -> Date_Position_O

Time converstion, how to convert 12 hour format into 24 hour format using c...

how to convert 12 hour format into 24 hour format using c program

Circular queue, explain implementation of circular queue insert,delete oper...

explain implementation of circular queue insert,delete operations

Illustrate hls colour model, HLS Colour Model  This model has the doub...

HLS Colour Model  This model has the double-cone representation shown in Figure 3.40. The three colour parameters in this model are called hue (H), lightness (L), and Saturati

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd