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 controls the screen flow, What controls the screen flow? The SET ...

What controls the screen flow? The SET SCREEN and LEAVE SCREEN statements controls screen flow.

Are there any special rules about inlining, Are there any special rules abo...

Are there any special rules about inlining? Yes, there are some rules about inlining - a.) Any source files which used inline function should contain function's definition.

Estimate the circuit switched network, a) Total available bandwidth = 1 Mbp...

a) Total available bandwidth = 1 Mbps = 1000 Kbps Each user requires send data at the rate of = 500 kbps As it is circuit switched network we have to dedicate the bandwidth So the

Describe in brief about the internet, Describe in brief about The internet ...

Describe in brief about The internet Web sites need to be set up to maximise information supplied to customers and to ensure they are as self-contained and helpful as possible.

Mathematical applications, The current 32 and 64 bit machines can represent...

The current 32 and 64 bit machines can represent integers of around 9 digits and 30 digits respectively, while various scientific and mathematical applications have to represent in

What is typical storage hierarchy, Q. What is typical storage hierarchy? ...

Q. What is typical storage hierarchy? A typical storage hierarchy is displayed in Figure above. Though Figure shows only block diagram however it includes storage hierarchy:

Describe about the protection features present in ms access, If a programme...

If a programmer doesn't wish to make modifies to the document he can lock the document data and its code from more changes by changing the extension of the file system to .MDE. Cha

.rapid technology, Choose one area of rapid technological change in IT or C...

Choose one area of rapid technological change in IT or Computer Science and research and report on recent developments and the outlook for the future in the area that you have chos

What is an accessor in c++, An accessor is a class operation that does not ...

An accessor is a class operation that does not change the state of an object in C++. The access or functions require to be declared as const operations

Explain garbage collection, Explain Garbage collection In this method ...

Explain Garbage collection In this method two passes are made over the memory to identify new areas. In the first pass it traverses all pointers pointing to allocated areas an

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