How to calculate Required Time Complexity of any problem (please do not memorise it)

Revision en1, by sumitpatel, 2024-09-13 13:39:13

A computer approximately calculates 10^8 operations per second

And time taken by your program to run depends on its input only (most of the time considering same program and on same device)

So now suppose in question it is given that find factorial of a number and input is n where n<=1e6

so now suppose if here you ran a code of n^2 it means that the operation perfomed will be the square of input (approximately) so here your n is 1e6 (given above ) your operations will be ( 10^^6)^2 i.e 10 ^12 but the computer can perform only 10^8 operation in 1 sec 2 sec -> 2*10^8 3 sec -> 3*10^8 and so on it will take 10^12/10^8 which is 10^4 seconds to run this program

If you still are confused read below (same concept applies here too)

Suppose you are given some question and input as n<=10 so you can do this question in bigO(n) because it will take 10 operation which can be perfomed in 1 sec so you can n ^2 similarly and so on till n^7 because then n=10 so there will be approximately 10^7 operations which can be performed in 1 sec

We can similarly check for exponential function tooo


for example if your code has time complexity of 2^n and n is n<=10 then 2^10 = 1024 which is smaller than 10^8 which can be done in 1 sec but same code if given input is n<=100 so number of opertions will be 2^100 = 10^30 (which is obviously greater than 10^8 so we can think of more optimised approach)

Just use this concept and find the required complexity (mostly useful in Online Assesment or contest)where you sometimes bigO(n^2) works because n<=10^3 ( n^2 = (10^3)^2= 10^6 which is less than 10^ 8 so it will run

Tip_ mostly it is not required that if it has bigO(n) complexity it will run n<=1e8 because

TIme complexity = c*n where c is constant (based on number of for loops and input output and basic operations)

so always think number of operations performed by computer a little less than 1e8 if your code is too big ==================

If you understand it pls do the upvote (green wallah hi dabana)

Tags time limit, time compleixty

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sumitpatel 2024-09-13 13:39:13 2259 Initial revision (published)