Loop & Time
complexity
Prepared by :
14 Oct. 2024 Youssef Ebrahim AKA EngJoe
8:30 p.m.
Outline
do-while Nested
Loops while Loop for Loop
Loop loops
Statements break continue return
Time complexity O(n) O(n^2)
Loops
Loops, or iterative statements in C++, allow you to execute
a block of code repeatedly until a specific condition is met.
while Loop
while Loop
The while loop is used when the number of iterations is not known
beforehand, and the code block is executed as long as the specified
condition is true.
The simplest kind of loop is the while-loop. Its syntax is:
Problem A
Problem B
do while Loop
do while Loop
The do-while loop is similar to the while loop, but the
condition is checked after the execution of the code block,
ensuring the block runs at least once.
The simplest kind of loop is the while-loop. Its syntax is:
for Loop
for Loop
The for loop is used when the number of iterations is known
before entering the loop. It consists of three parts:
initialization, condition, and increment/decrement
Problem C
Problem D
Nested loops
loops can be nested within one another to create more
complex iteration patterns, allowing for multi-dimensional
processing or hierarchical data structures .
How to get this output ?
Problem E
Problem F
Break
VS continue
Break VS continue
"In C++, loops can be controlled using 'break' and 'continue' statements:
- 'break': Exits the loop prematurely.
- 'continue': Skips the current iteration and proceeds to the next."
linear search
Answer
Time complexity
Time complexity
C++ is known for its efficiency and speed.
Typically can handle up to 10^8
operations in a reasonable time frame.
Time complexity
Generally, the time limit for running your code on platforms like
Hackerrank, Atcoder, Codeforces, etc. is 1-2 seconds. So, we need
to write an efficient code that passes this time limit constraint.
Big Oh (O)
It represents the upper bound of a function
Used to approximate time complexity of a code
Time complexity
If you have function f(x), then consider a function g(x) such that
f(x) <= c.g(x)
For all values of x>=x0 for some value of x0
Then we say, f(x) = O ( g(x) )
Eg. 1:
If f(n) = n - 2
f(n) <= 8.n
f(n) <= 8.g(n)
Where g(n) = n
By definition, f(n) = O(n)
Time complexity
Eg. 2: If f(n) = 3n^2 + 5n + 8
By definition of Big Oh, f(n) = O(n^2)
Eg. 3: If f(n) = 3n^3 + 2n
By definition of Big Oh, f(n) = O(n^3)
In polynomial functions, only see the highest degree term to find Big Oh
Find time complexity
of this code.
i=0; will run only 1 time
i<n; will be run n+1 times
i++ will be run n times
cout<<A[i]; will be run n times
Time complexity
= 1 + n+1 + n + n = 3n + 2 Time complexity: O(1) [constant]
= O(n)
Find time complexity
of this code.
i=0; inner loop will run 0 times
i=1; inner loop will run 1 times
i=2; inner loop will run 2 times
….
i=n-1 ; inner loop will run n-1 times
Total steps = 0 + 1 + 2 + …. + n-1
= (n * (n-1)) /2
= O(n^2)
Problem G
Find time complexity
of this code.
For i=1, 2, 4, 8, 16, ….., 2k
Let us assume that it breaks out of loop in k steps
1.(2k) > n
2k > n
k approximately log2 (n)
Time complexity: O( log2 (n) )
What is the output ?
for more
Common errors in online platforms
Compiler error (CE)
Indicated by compiler itself with the line number in which there is error
Wrong Answer (WA)
eg. Yes not = YES
Read the input and output format in the question very carefully
Time Limit Exceeded (TLE)
Time limit is generally 1 second. And if your code is slow to pass this time limit, you will
get this error.
