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

How the characters used in operand data type, Q. How the Characters used in...

Q. How the Characters used in operand data type? A common form of data is character or text strings. Characters are signified in numeric form mostly in ASCII (American Standard

What are pooled tables, Normal 0 false false false EN-I...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Neural networks, Given a collection of DNA sequences (it can be downloaded ...

Given a collection of DNA sequences (it can be downloaded in the assignment directory), where true binding sites as positive examples have been provided. The objective of this assi

What are packages, What are packages? Package is a group of elements (c...

What are packages? Package is a group of elements (classes, generalizations, associations and lesser packages) with a common theme. Package partitions a model making it simpler

BCD ADDER, create a BCD adder combinational ckt. that adds 2 digit BCD inpu...

create a BCD adder combinational ckt. that adds 2 digit BCD inputs

Differentiate between http and ftp, Differentiate between http and ftp. ...

Differentiate between http and ftp. HTTP and FTP were developed to make Internet transmission better. FTP is utilized to exchange files among computer accounts, to transfer

Determine about the stack organization, Stack Organization The CPU of t...

Stack Organization The CPU of the most computers comprises of stack or called as last-in-first-out (LIFO) list in which information is stored in such a manner that item stored

What is asynchronous reset, What is Asynchronous Reset? Asynchronous re...

What is Asynchronous Reset? Asynchronous reset: The biggest problem along with asynchronous resets is the reset release, which termed as reset removal. By using an asynchron

What are user threads, What are User threads   User threads are support...

What are User threads   User threads are supported above the kernel and are executed by a thread library at the user level. Thread creation & scheduling are done in the user sp

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