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

Operating system, explain the various types of computer systems

explain the various types of computer systems

Backward chaining - artificial intelligence, Backward Chaining - Artificial...

Backward Chaining - Artificial intelligence Given that we are just interested in constructing the path, we may set our initial state to be the theorem statement and search backw

objectives- parallel computing, Objectives After going through this un...

Objectives After going through this unit, you will be able to : Tell historical facts of parallel computing; Can explain the essential concepts of the discipline, e.g.

Difference between the functions unlink and unset?, Unlink() is a function ...

Unlink() is a function for file system handling. It will easily delete the file in context.   Unset() is a function for variable management. It will create a variable undefin

How speech is transmitted in a digital switching environment, How speech is...

How speech is transmitted in a digital switching environment using PCM/TDM? A digital carrier system is a communications system which uses digital pulses quite than analogue si

Simulate a worm propagation considering traffic delay, At time t when an in...

At time t when an infected machine scans and finds a vulnerable machine, the vulnerable one will be compromised and start to scan and infect others at time t+X, where X is a r.v. f

Show synchronous mode for point-to-point message passing, Q. Show Synchrono...

Q. Show Synchronous mode for point-to-point message passing? Synchronous mode: Transmitting can be started whether or not matching receive has been started, but transmitting w

Conversion of bcd number to binary using a procedure, Q. Conversion of BCD ...

Q. Conversion of BCD number to binary using a procedure? Conversion of BCD number to binary using a procedure. Algorithm for conversion procedure: Take a packed BCD digit

Add the equation by using 2's compliment, Add 20 and (-15) using 2's comple...

Add 20 and (-15) using 2's complement ? Ans. Addition of 20 and (-15) by using 2's complement as (20) 10 = 1 0 1 0 0                                                  (16

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