Skip to main content

Time and Space complexity : What does time and space complexity mean?

 Time and Space complexity

                                icancodebetter.blogspot.com

Time 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 also known as worst case time complexity as it denotes the upper bound in which 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 also known as best case time complexity as it denotes the lower bound in which algorithm terminates.
3. !-notation: It is used to denote the average time of a program.

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.


Instagram 👇 

For more Queries

Labels:

Comments

Post a Comment

Popular posts from this blog

Loops in C++ : What is loop and types of loop in C++?

 Loops In computer programming, loops are used to   repeat a block of code  . For example, let's say we want to show a message 1000times , Then instead of writing the print statement 1000 times, we can use a loop. Type of loops 1. For loop 2. While loop 3. Do while loop For loop  For loop uses an external variable to control the execution. A for loop takes into account the                                           Initialization Condition checking Incrementation In its syntax itself. The syntax is shown below:- For(initialization;condition;incrememt){ //body } While loop  Imagine we had to print “Hello World” 100 times or n-number of times. Would it be wise to write cout << “Hello World\n” 100  times. While loops help us automate this. Sometimes, the loop also uses an external initialization and incrementation logic to control how many times t...
1 comment
Read more

Algorithm : What is algorithm and what are its characteristics?

 Algorithm Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. Qualities of a good algorithm 1. Input and output should be defined precisely. 2. Each step in the algorithm should be clear and unambiguous. 3. An algorithm shouldn't include computer code. Instead,the algorithm should be written in such a way that it can be used in different programming languages. Good, logical programming is developed through good pre-code planning and organization. This is assisted by the use of pseudocode and program flowcharts Instagram 👇  For more Queries
Post a Comment
Read more