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

Illustrate the ftp commands, Q. Illustrate the FTP commands? FTP includ...

Q. Illustrate the FTP commands? FTP includes many commands however only few are used to retrieve a file. A user is required to understand the three basic commands to connect to

Determine the object oriented principles, Determine the Object oriented pri...

Determine the Object oriented principles Many latest applications are being developed based on object oriented principles such as methods, classes, and inheritance. To fulfil

When page fault frequency in an operating system is reduced, Page fault fre...

Page fault frequency in an operating system is reduced when the? When locality of reference is appropriate to the process so Page fault frequency in an operating system is redu

Describe the types of flip-flops and latches, Describe the types of flip-fl...

Describe the types of flip-flops and latches. Flip-flops are of two types as illustrated below: a. Positive edge triggered b.  negative edge triggered Latches are

While using ftp what is wildcard expansion in file names, While using FTP w...

While using FTP what is wildcard expansion in file names? To make this easy for users to identify a set of file names, FTP permits a remote computer system to perform usual fil

Computer graphics, What is intractive graphics and user dialouge in comput...

What is intractive graphics and user dialouge in computer graphics

Applications of electronic data interchange in business, What are the appli...

What are the applications of Electronic Data Interchange in business? The applications of Electronic Data Interchange are as given below: 1. Organisations that use EDI 2

Objectives-parallel computer architecture , Objectives After going thro...

Objectives After going through this part, you will be capable to: Examine the meaning of Pipeline processing and explain pipeline processing architectures; Classify

Parallel virtual machine, PVM is mainly a simulation of a computer machine ...

PVM is mainly a simulation of a computer machine running parallel programs. It is a software package that allows a heterogeneous collection of UNIX and/or Windows computers hooked

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