1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | namespace TimeComplexity { class Program { static void Main(string[] args) { char[] arr = { 'a', 'b', 'b', 'd', 'e' }; char invalidChar = 'b'; int ptr = 0, n = arr.Length; for (int i = 0; i < n; i++) { if (arr[i] != invalidChar) { arr[ptr] = arr[i]; ptr++; } } for (int i = 0; i < ptr; i++) { Console.Write(arr[i]); Console.Write(' '); } Console.ReadLine(); } } } |
Output
a d e
To calculate Complexity
Consider following statements
char[] arr = { 'a', 'b', 'b', 'd', 'e' };
char invalidChar = 'b';
int ptr = 0, n = arr.Length;
char[] arr = { ‘a’, ‘b’, ‘b’, ‘d’, ‘e’ }; This will be executed N times
char invalidChar = ‘b'; This will be executed 1 time
int ptr = 0; This will be executed 1 time
N = arr.Length; This will be executed 1 time
Console.ReadLine(); This will be executed 1 time
Note: The character array initialization will actually execute N times. This is because you are assigning one character at a time.
char invalidChar = ‘b'; This will be executed 1 time
int ptr = 0; This will be executed 1 time
N = arr.Length; This will be executed 1 time
Console.ReadLine(); This will be executed 1 time
Note: The character array initialization will actually execute N times. This is because you are assigning one character at a time.
N + 4
Consider the following for loop
for (int i = 0; i < n; i++)
{
if (arr[i] != invalidChar)
{
arr[ptr] = arr[i];
ptr++;
}
}
int i=0; This will be executed only once. The time is actually calculated to i=0 and not the declaration.
i<N; This will be executed N+1 times
i++ ; This will be executed N times
if(arr[i]!=invalidChar) This will be executed N times
arr[ptr]=arr[i]; This will be executed N times (in worst case scenario)
ptr++; This will be executed N times (in worst case scenario)
{1+(N+1)+N}+N+N+N = 5N+2
Consider the following for loop
for (int i = 0; i < ptr; i++)
{
Console.Write(arr[i]);
Console.Write(' ');
}
{1+(N+1)+N}+N+N = 4N+2
Adding everything up I get
(N+4)+(5N+2)+(4N+2) = 10N+8
So the asymptotic time complexity for the above code is O(N), which means that the above algorithm is a liner time complexity algorithm.
Article by Pranavkarambiam@gmail.com- (Srivatsa)
Post a Comment