How to find T(n) of the following code. I need an analysis.
void abc(int n) {
for(int i = 0; i<n; i++){
for(int j = 0; j<i; j++){
System.out.println("Hello World");
}
}
}
Add a comment
|
2 Answers
The complexity is O(N^2).
In detail the no. of computations are:
T(N) = 1 + 2 + 3 + ...... + n = n(n+1)/2
So O(N^2)
2 Comments
Khalid Habib
it will be n(n-1)/2
Akashdeep Saluja
@KhalidHabib No, it will be n+1 only.
To calculate Complexity for loop in program, for that you can check number loop declare in program and then check how deep the call with nesting.
In this code complexity will raise by one loop and then another inner-loop, so it raise to O(N^2).
However, outerloop will be n sequentially and inner loop will be i+1, so sequentially it will be 1+2+3...n, hence this will be calculate as n*(n+1)/2, and ultimately it will lead to O(N^2).
