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

Sorting Techniques : Selection Sort , Bubble Sort , Insertion Sort

Sorting Techniques 1. Selection Sort: Idea: The inner loop selects the minimum element in the unsorted array  and places the elements in increasing order. Time complexity: O(N 2 ) #include <iostream> using namespace std; int main() {     int n;     cin>>n;   int arr[n];    for(int i=0;i<n;i++){          cin>>arr[i];   }  for(int i=0;i<n-1;i++){       for(int j=i+1;j<n;j++){            if(arr[j]<arr[i]){                 int temp =arr[j];                  arr[j]=arr[i];             arr[i]=temp;           }           }      }for(int i=0;i<n;i++){       cout<<arr[i]<<" ";    }   return 0; } 2. Bubble Sort: Idea: ...
1 comment
Read more

How to check if a number is prime in C++ | How to generate Armstrong numbers in C++?

How to check if a number is prime in C++  Prime Numbers Prime numbers are numbers which have only 2 distinct factors i.e 1 and the number itself. Eg. 2,3,5,7,19 etc. Ques1. Write a program to check if a number is prime or not. #include <iostream> #include<cmath> using namespace std; int main() { int n; cin>>n; bool flag=0; for(int i=2;i<=sqrt(n);i++){ if(n%i==0){ cout<<"Non-prime"<<endl; flag=1; break; } } if(flag==0){ cout<<"prime"<<endl; } return 0; } How to generate Armstrong numbers in C++ Armstrong Numbers Armstrong numbers are numbers which have their sum of cube of individual digits equal to the number itself. E.g 153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153. #include <iostream> #include<math.h> using namespace std; int main() { int n; cin>>n; int sum=0; int originaln=n; while(n>0){ int lastdigit= n%10; sum+= pow(lastdigit,3); n=n/10; } if(sum==originaln){ cout<<"Armstrong number"...
Post a Comment
Read more

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