[go: up one dir, main page]
Scribd
Upload
6 views13 pages

Intro to Time Complexity

The document explains time complexity, focusing on how to measure the time taken by a program based on the number of primitive operations and input size. It emphasizes the importance of considering the worst-case scenario, represented by Big O notation, to determine the maximum running time of code. Examples illustrate how to calculate time complexity for different operations and the implications of exceeding time limits in programming contests.

Uploaded by

abdullahelfayed901
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
6 views13 pages

Intro to Time Complexity

The document explains time complexity, focusing on how to measure the time taken by a program based on the number of primitive operations and input size. It emphasizes the importance of considering the worst-case scenario, represented by Big O notation, to determine the maximum running time of code. Examples illustrate how to calculate time complexity for different operations and the implications of exceeding time limits in programming contests.

Uploaded by

abdullahelfayed901
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 13

Time Complexity

How much time does it take to run a program code ?

Time can be calculated by the maximum number of primitive


operations that the program execute.

Operations like: addition , assignments, loops…etc.

But How we calculate it ?


Let me ask you a question ?
what if we make 10 inputs then make 40000 inputs
according to time?
Actually, the time of 40000 inputs is more than the time of
10 inputs. So the time depends on the input size.

We should always consider the Worst Case of time not the


best nor the average.

Because the Time Limit will depend only on Worst case.


What is the worst case time complexity also called (Big O)
notation ?

● The worst-case time-complexity is the longest


running time performed by a program code
given an input size n
EXAMPLE : ● Given n numbers (1 <= n <= 100000), you are
asked to print the sum of these n numbers

● How to calculate the


time complexity of
this code?
● Given n numbers (1 <= n <= 100000), you are
asked to print the sum of these n numbers
● How to calculate the
time complexity of
this code?
● As shown in the code, we
did n addition operations (i+
+), n assignment operations
(cin>>x), and another n
addition operations (sum
+= x), so the total is 3n
operations

● We said it’s O(n) where the


maximum value for n is
100000
● Big O notation is a mathematical notation that used in computer science
to calculate the upper bound of code complexity or maximum time
complexity
● Given 1 <= n <= 100000, 1<= m <= 1000
Number of Operations Big O notation

5 O(1)

2m + n + 2 O(n)

m^2 + 2n + 5 O(m^2)

m*n+n+m O(m*n)

n * log(n) + m * log(m) O(n*log(n))

nlog(n) + m^2 + n! O(n!)


This shows the relationship between the input size
and the different time complexities
Time Limit Exceeded
● one second can hold more than 10^7 operations.
But, your code should not be more than 10^7 operations.
This because of some reasons like the ignored factors in
Big O notation and the online judges limitations like
codeforces.

● So if you are given n (1 <= n <=100000) and the time


limit is one second, and your complexity is O(nlog(n))
which is about 10^6, so it’s fine

● But if your complexity is O(n^2) which is about 10^10, you


will get Time Limit Exceeded

You might also like