Time Complexity and space Complexity.

By

■♧ Time & Space Complexity->

Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. 

■ Types of notations ->

1. O-notation->

It is used to denote asymptotic upper bound. For a given function g(n), we denote it by O(g(n)). Pronounced as “big-oh of g of n”. It is also known as worst case time complexity as it denotes the upper bound in which the algorithm terminates. 

2. Ω-notation->

It is used to denote asymptotic lower bound. For a given function g(n), we denote it by Ω(g(n)). Pronounced as “big-omega of g of n”. It is also known as best case time complexity as it denotes the lower bound in which the algorithm terminates. 

3. 𝚯-notation->

 It is used to denote the average time of a program. 


Linear Time Complexity  O(n) 

Comparison of functions on the basis of time complexity 

It follows the following order in case of time complexity: 

O(nn) > O(n!) > O(n3) > O(n2) > O(n.log(n)) > O(n.log(log(n))) > O(n) > O(sqrt(n)) > O(log(n)) > O(1) 

Note: Reverse is the order for better performance of a code with corresponding time complexity, i.e. a program with less time complexity is more efficient. 


■》Space Complexity ->

Space complexity of an algorithm quantifies the amount of space  taken by a program to run as a function of length of the input. It is directly proportional to the largest memory your program acquires at any instance during run time. 

■ For example:

 int consumes 4 bytes of memory.

Comments

Post a Comment

Popular posts from this blog

Introduction of java Programming language.

By
Image
■》Variables & Data Types & constant  -> ● Variables->                         ○ A variable is a container (storage  area) used to hold data.  ○ Each variable should be given a unique name  (identifier).   ■ Program-> public class Main  {    public static void main(String[] args)  {       // Variables        String name = "ved";        int age = 19;        float price=399.50;        String neighbour = "duggu";        String friend = "shourya";    } } ● Data Types-> Data types are declarations for variables. This determines the type and size of data associated with variables which is essential to know since different data types occupy different sizes of memory. There are 2 types of Data Types : 1● Primitive Data types : to store simple...
Read more

Stack data structure.

By
Image
■ what is stack?                             Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies that the element that is inserted last, comes out first and FILO implies that the element that is inserted first, comes out last.   ■ Diagram-                              ■  real life example-                                                                There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate whic...
Read more