Skip to main content

Describe best case, average case and worst case complexity of an algorithm.

By

Best case complexity gives the lower bound on the running time of the algorithm for any instance of inputs. This indicates that the algorithm can never have lower running time that best case for particular class problems.
Worst case complexity gives the upper bound in the running time of the algorithm for all the instances of inputs this insures that no input can overcome the running time limit processed by worst case complexity.
Average case complexity gives average number of steps required on any instance of inputs.

For example: the best case for a simple sorting algorithm would be providing data that is already sorted, worst case for the same algorithm would be providing input that is sorted in reverse order and average case would be  input that is half sorted. This varies according the algorithm as this would not be the case for all sorting algorithms
Labels:

Comments

Post a Comment

Popular posts from this blog

SAP-1(Simple as Possible-1) Computer Architecture Introduction

By
The Simple-As-Possible (SAP)-1 computer is a very basic model of a microprocessor explained by Albert Paul Malvino. The SAP-1 design contains the basic necessities for a functional Microprocessor. Its primary purpose is to develop a basic understanding of how a microprocessor works, interacts with memory and other parts of the system like input and output. The instruction set is very limited and is simple. The features in SAP-1 computer are: W bus – A single 8 bit bus for address and data transfer.  16 Bytes memory (RAM)  Registers are accumulator and B-register each of 8 bits.  Program counter – initializes from 0000 to 1111 during program execution.  Memory Address Register (MAR) to store memory addresses.  Adder/ Subtracter for addition and subtraction instructions.  A Control Unit  A Simple Output.  6 machine state reserved for each instruction  The instruction format of SAP-1 Computer is (XXXX) (XXXX) A Simple animation to demonstrate the working of SAP I:
3 comments
Read more

[FIX]Illuminate\Database\QueryException SQLSTATE[HY000] [2054] The server requested authentication method unknown to the client (SQL: select * from information_schema.tables where table_schema = enrolmentsystem and table_name = migrations and table_type = 'BASE TABLE')

By
Illuminate\Database\QueryException    SQLSTATE[HY000] [2054] The server requested authentication method unknown to the client (SQL: select * from information_schema.tables where table_schema = enrolmentsystem and table_name = migrations and table_type = 'BASE TABLE')   at vendor/laravel/framework/src/Illuminate/Database/Connection.php:678     674▕         // If an exception occurs when attempting to run a query, we'll format the error     675▕         // message to include the bindings with SQL, which will make this exception a     676▕         // lot more helpful to the developer instead of just the database's errors.     677▕         catch (Exception $e) {   ➜ 678▕             throw new QueryException(     679▕                 $query, $this->prepareBindings($bindings), $e     680▕             );     681▕         }     682▕        +33 vendor frames    34  artisan:37       Illuminate\Foundation\Console\Kernel::handle(Object(Symfony\Component\Console\Input\ArgvInput),
1 comment
Read more