Test your knowledge!Take a quiz to access yourself.

Improve program efficiency by reducing complexity

Do you wonder why and how to improve your program efficiency?

We are living in electronic era with computers having high speed processor and memory. So, if we write slow software(complex codes) it does not effect much in cost of Time of execution and Space to execute with large space and high speed processors.But, if these kind of complex codes runs in some limited space and calculate there execution time most of the codes will fail.

To increase program efficiency as a good programmer is a challenge , in order to that you need to think about two things :

  • Time Complexity
  • Space Complexity
  1. Time Complexity:

Performing an accurate calculation of a program’s operation time is a very labor-intensive process (it depends on the compiler and the type of computer or speed of the processor). Therefore, we will not make an accurate measurement; just a measurement of a certain order of magnitude.

Complexity can be viewed as the maximum number of primitive operations that a program
may execute.Time complexity is denoted by O notation called as Big-O notation

Here is a piece of pseudo code by which we can have a look to time complexity :

function printNvalues(int N){

int result=0;

for(int i=0;i<N;i++){                    // Here is the code which will execute N number of time so, the time complexity is O(N)

result+=1;

}

return result;

}

Factors effecting Time Complexity :

  • Operations
  • Comparisons
  • Loop stuff
  • Pointer reference
  • Function call of out side

How to measure Time complexity :

  1. Constant time complexity O(1) : Their is always fixed number of operation and time complexity always remain same

def constant(n):
result = n * n  // Its complexity is O(1)
return result

2. Logarithmic time : O(log N): The value of n is halved on each iteration of the loop. If n = 2 x then log n = x. How long
would the program below take to execute, depending on the input data?

def logarithmic(n):
result = 0
while n > 1:
n //= 2
result += 1
return result

3. Linear time O(N): Let’s note that if the first value of array A is 0 then the program will end immediately. But
remember, when analyzing time complexity we should check for worst cases. The program
will take the longest time to execute if array A does not contain any 0.

def linear(n, A):
for i in xrange(n):
if A[i] == 0:
return 0
return 1

4. Similarly O(N*N) complexity :

def quadratic(n):
result = 0
for i in xrange(n):
for j in xrange(i, n):
result += 1
return result // Here this piece of code have 2 loops and so it will execute N*N number of times

Time complexity in ascending order
Time complexity in ascending order

2. Space Complexity :

More specifically, space complexity is the amount of memory needed to perform the computation. It includes all the variables, both global and local, dynamic pointer data-structures and, in the case of recursion, the contents of the stack.Depending on the convention, input data may also be included.

Factors effecting space complexity :

  • Variable
  • Data Structure
  • Allocations
  • Function calls

The way we use data structure in our program effects our space complexity.

For , example if you want to store few values of int and you declared double as variable than it will create more room in memory to execute the program .In other examples like using tree instead of linked list for sorted lists will enhance your program’s overhead of sorting the list again.

Add a Comment

Your email address will not be published. Required fields are marked *