Example of asymptotic notations, Computer Engineering

Assignment Help:

Q. Example of asymptotic notations?

The function f (n) belongs to the set  (g(n)) if there exists positive constants c such that for satisfactorily large values of n we have 0<= c*g(n) <=f(n). In another words,

  O(g(n)) ={ 0<= c*g(n) <=f(n) for all n >= no }.    

Assume we have a function f (n) = 4n2 + n then order of function is O(n2). The asymptotic notations give information about the upper and lower bounds on complexity of an algorithm with help of O and ? notations. E.g. in the sorting algorithm the upper bound is O (n ln n) and lower bound is ? (n ln n). But problems such as matrix multiplication have complexities such as O (n3) to O (n2.38).

Algorithms that have similar lower and upper bounds are called optimal algorithms. So a few sorting algorithms are optimal whereas matrix multiplication based algorithms are not.


Related Discussions:- Example of asymptotic notations

What are the applications of edi in business, What are the applications of ...

What are the applications of EDI in business A.  Organistions that use EDI Extensive users of EDI contain: BHS- is a UK and European retailer dealing majorly in appare

Determine a ring counter that consisting of five flip-flops, A ring counter...

A ring counter consisting of five Flip-Flops will have ? Ans. A ring counter have 5 states while consisting of Five Flip-Flops.

Describe the horizontal frequency or cycle, Q. Describe the Horizontal Freq...

Q. Describe the Horizontal Frequency or cycle? Horizontal Frequency: The time to scan one line connecting the right edge to left edge of the screen horizontally is known as t

Difference between non-relocatable self relocatable programs, Differentiate...

Differentiate between non-relocatable self relocatable programs. A non-relocatable program is one which cannot be executed in any memory area other than the area starting at

Programming languages array operations, Q. Programming languages array oper...

Q. Programming languages array operations? In programming languages array operations are written in compact form which frequently makes programs more understandable. Conside

Tag do you use to add a hyperlink column to the DataGrid, What tag do you u...

What tag do you use to add a hyperlink column to the DataGrid?   Anchor tag is used to add a hyperlink column to the data grid

What is a work process, What is a work process? A work process is where ...

What is a work process? A work process is where individual dialog steps are in fact processed and the work is done.  Every work process ocuurs one type of request.

Databse, defination of query ?

defination of query ?

Determine about the blocking suspicious behaviour, Determine about the bloc...

Determine about the blocking suspicious behaviour The response could be spontaneous and automatic, with an option to generate the alert message manually. The history recorded i

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