Skip to main content

Time & Space Complexity | Time & Space Complexity in java and DSA | (Lecture 8 )

Java - Introduction to Programming

Lecture 8



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. 


Examples : 








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 time 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.

Labels

Labels:

Comments

Post a Comment

Popular posts from this blog

Enter 3 numbers from the user & make a function to print their average in java, c++, python, java.

Enter 3 numbers from the user & make a function to print their average. To find the average of three numbers, you need to add the three numbers together and then divide the sum by three. Here's how you can write a function in C++, C, Python, and Java to take three numbers from the user and calculate their average: JAVA import java . util .*; public class Solutions {     public static void main ( String args []) {        Scanner sc = new Scanner ( System . in );        int a = sc . nextInt ();        int b = sc . nextInt ();        int c = sc . nextInt ();          int average = ( a + b + c ) / 3 ;        System . out . println ( average );    }    }   C++: // c++ #include <iostream> using namespace std ;...
Post a Comment
Read more

Top Beginner Patterns in Java: How to Print Star, Number and Character (Lecture 5)

 Java - Introduction to Programming Lecture 5 Patterns - Part 1 import java . util .*;   public class Patterns {     public static void main ( String args []) {         int n = 5 ;         int m = 4 ;         for ( int i = 0 ; i < n ; i ++) {             for ( int j = 0 ; j < m ; j ++) {                 System . out . print ( "*" );            }             System . out . println ();        }    } }   import java . util .*;   public class Patterns {     public static void main ( String args []) {     ...
Post a Comment
Read more

Merge Sort | How do I learn merge sort?

       Merge Sort | For Beginners | Java Placement Course >> Merge sort is a popular sorting algorithm that utilizes a divide-and-conquer approach to sort elements in an array. The basic idea behind merge sort is to divide an unsorted array into two halves, recursively sort each half, and then merge the two sorted halves into a single sorted array. >>  Merge sort algorithm works by recursively dividing an array into two halves, sorting each half, and then merging them to obtain the sorted array. The basic steps of the merge sort algorithm are as follows: Divide the unsorted array into two halves, mid and left. Sort the left half recursively using merge sort algorithm. Sort the right half recursively using merge sort algorithm. Merge the two sorted halves to obtain the final sorted array. JAVA Implementation: // Merge sort public class MergeSort {     //time complexity=nlogn     public static void conquer ( int arr [], int ...
Post a Comment
Read more