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:

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

2D Arrays | Java Complete Placement Course | Lecture 11

Java - Introduction to Programming Lecture 11 2D Arrays In Java It is similar to 2D matrices that we studied in 11th and 12th class. Creating a 2D Array - with new keyword int [][] marks = new int [ 3 ][ 3 ] ; Taking a matrix as an input and printing its elements. import java . util .*;   public class TwoDArrays {     public static void main ( String args []) {         Scanner sc = new Scanner ( System . in );         int rows = sc . nextInt ();         int cols = sc . nextInt ();           int [][] numbers = new int [ rows ][ cols ];           //input         //rows         for ( int i = 0 ; i < rows ; i ++) {             //columns  ...
Post a Comment
Read more

Conditional Statements | if, If-else, "if" and "if else", Switch Break | Complete Java Placement Course | Lecture 3

                                    Java - Introduction to Programming Lecture 3 Conditional Statements Conditional statements are a fundamental concept in programming. They are used to make decisions based on certain conditions, allowing the program to perform different actions depending on the input or data it receives. In this article, we'll take a closer look at conditional statements in programming and how they can be used effectively. What are conditional statements? Conditional statements, also known as "if-then" statements, are used in programming to execute certain code if a condition is met. In other words, the program will perform a particular action if a particular condition is true. For example, a program may check if a user has ent...
Post a Comment
Read more