Answer:
Step-by-step explanation:
O(N*N) or O(N2).
Explanation:
The time complexity can be measured by caculating the number of times the loop will execute.
The above code runs total no of times
= N + (N – 1) + (N – 2) + … 1 + 0
= N * (N + 1) / 2
= 1/2 * N^2 + 1/2 * N
O(N^2) times.
Thus Time complexity is O(N*N) or O(N2).
When i=0, it will run 0 times.
When i=1, it will run 1 times.
When i=2, it will run 2 times and so on.
So the time complexity will be O(N*N) or O(N2).
The function O(n2) has a complexity that is proportional to the square of the input size.
O(n2) with 2 total iterations.
O(N^2) is for → 2 nested “for loops”
We usually want to know how many steps an algorithm will take for an input of size ‘N' when calculating complexity.
This example contains two ‘for' loops, each of which will execute ‘N' times for each element ‘N'. As a result, it will run N2 times in total. In large O notation, we'd state the complexity of this algorithm is O(N2).
Time Complexity:
The amount of time it takes an algorithm to finish a computation.
What factors contribute to the complexity of time?
Looping (for, while)
Big O Notation:
The language and metric we use to describe how long an algorithm takes to run.
O(n²) Quadratic Time
Two nested loops are involved.
Each item from two different collections must be compared to one another.
Space Complexity:
Space complexity is the measurement of memory (space) that an algorithm requires, similar to time complexity.
What determines the complexity of space?
Variables
Allocations
Space Complexity: O(1) space
Because of the nested for loops The time complexity is going to be quadratic.
As a result, the Space Complexity will be O(1) space.
Worst case space complexity: O(1)
Hence,
Time Complexity: O(n²)
Space Complexity: O(1)