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

Operators in C++ : What are the different types of operators in C++?

Operators in C++ Operators are nothing but symbols that tell the compiler to perform some  specific operations. Operators are of the following types - 1. Arithmetic Operators Arithmetic operators perform some arithmetic operation on one or two  operands. Operators that operate on one operand are called unary  arithmetic operators and operators that operate on two operands are  called binary arithmetic operators. +,-,*,/,% are binary operators. ++, -- are unary operators. Pre-incrementer : It increments the value of the operand instantly. Post-incrementer : It stores the current value of the operand temporarily  and only after that statement is completed, the value of the operand is  incremented. Pre-decrementer : It decrements the value of the operand instantly. Post-decrementer : It stores the current value of the operand temporarily  and only after that statement is completed, the value of the operand is  decremented. Example - int a=10; int b; ...
Post a Comment
Read more

Compiler And Interpreter

Compiler vs interpreter  Compiler is a computer program that translates a program written in a high-level language to the machine language of a computer which can easily understand by the machine or computer . The high-level program is referred to as the "source code".The compiler is used to translate source code into machine code or compiled code. This does not yet use any of the input data. When the compiled code is executed, referred to as 'running the program,' the program processes the input data to produce the desired output. Interpreter is a computer program that directly executes instructions line by line written in a programming language, without requiring them previously to have been compiled into a machine language program. Instagram 👇  For more queries
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