Big O asymptotic analysis/Big O notation

Big O asymptotic analysis/Big O notation 

Big O is one of the most fundamental tools for computer scientists to analyse the cost of an algorithm. Big O notation is used to calculate the runtime of the best, worse and expected case scenario. Big O only cares about the worse case scenario. 

This is a way of comparing multiple solutions which solve the same problem, to find out which solution is the most efficient in terms of time and space complexity. For example they are multiple ways to drive to Liverpool football Club however lets choose the way that is quickest (time complexity) and is least stressful so it takes up less head space for the driver (space/memory complexity). 

Time Complexity 

How long does the algorithm take to complete?

In the worse case scenario how long will it take to complete this algorithm? 

The execution time of a task in relation to the number of steps required to complete it.


Example: Quick Sort

Worse case= O(N2) - the pivot keeps getting the highest value

Best case= O(N) - if all elements are equal the array will only be traversed once 

Expected case= O(N Log N)


Space Complexity 

How much space does this algorithm need for this computation?

In the worse case scenario how much space will it take to complete this algorithm?

Amortized Time Complexity
average time taken per operation, if you do many operations. ArrayList resizing example 




Comments

Post a Comment

Popular posts from this blog

Basic Overview of Microsoft Azure?

Image
Microsoft Azure is a cloud computing service created for building, testing, deploying, and managing applications and services through their numerous data centres around the world. Typically, you only pay for cloud services you use, helping you lower your operating costs, run your infrastructure more efficiently and scale as your business needs change.Here are a few of the many services you can do with Azure(If you don't understand these services just yet, don't worry I will create another article for each of these services):  - SQL databases - App services for web and mobile applications. - Active Directory Users and Groups - Virtual Machines Cloud Computing: In the simplest terms, cloud computing means storing and accessing data and programs over the Internet instead of your computer's hard drive. The cloud is just a metaphor for the Internet. Data Centres: A place that stores, manages and distributes its data. Azure currently has data centres in 140 countries...
Read more

Understanding the basics of REST API with HTTP and JSON

Image
What is an API? The Messenger  API stands for Application Programming Interface.The API is the messenger that takes REQUESTS and tells the system what you want to do and returns a RESPONSE back to you. This allows two pieces of software to communicate with each other. Metaphor example: Waiter at a restaurant gets the REQUEST from customer and tells the Kitchen what to do and then delivers the RESPONSE back to the customer. One of the most popular types of API is REST or, as they’re sometimes known, RESTful APIs. What is REST ? Let us use HTTP requests to format those messages  The short answer is that REST stands for Representational State Transfer. Architecture style for designing network applications which are are stateless, meaning that the server does not need to know anything about what state the client is in and vice versa. In other words REST is a set of rules/standards/guidelines that follow the REST specification, basically governs the behaviour of clients a...
Read more