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

Define optimistic synchronization, Q. Define Optimistic Synchronization? ...

Q. Define Optimistic Synchronization? Optimistic Synchronization: This method too updates atom by requester process however sole access is granted after atomic operation by abo

Define about pascaline - mechanical computers, Pascaline:Mechanical compute...

Pascaline:Mechanical computers Blaise Pascal made the initial attempt in the direction of this automatic computing. He invented a apparatus, which comprised of lots of gears an

Describe about managing data tasks?, Data can be handled by using the featu...

Data can be handled by using the features of Import text wizard and export text wizard. Here you can keep the operation for future use. First you should edit the specification name

Pre order given find post order ?, The preorder traversal sequence of a bin...

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

What is the difference between intranet and extranet, What is the differenc...

What is the difference between intranet and extranet? Given table illustrates brief overview of the differences among the three kinds of the network: Network

Requirements for cache simulator, Using your cache simulator and using smal...

Using your cache simulator and using smalltex.din as your memory trace determine the total miss rate, compulsory miss rate, capacity miss rate, and conflict miss rate for the follo

Why should i use cgi, CGI is significant whenever you require to retain sta...

CGI is significant whenever you require to retain state information about a user, or run an application which communicates with the server. Things like guestbook's, Chat clients, d

Boundary tag management system, what are the two memory management scehme...

what are the two memory management scehme(boundary tag system,buddy system)

Codevita test, provide answers for Luminous Jewels - The Polishing Game?

provide answers for Luminous Jewels - The Polishing Game?

Cache memories - computer architecture, Cache Memories - computer architect...

Cache Memories - computer architecture: Speed of the primary memory is very low in comparison with the speed of processor For well performance, the processor can't spend

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