Some basic doubts in Algorithms and complexity..

Replies

• 

  RajdeepCE

  I know the 1st answer, for the 2nd and 3rd answer I need to refer book.
  Time complexity it means the time taken to compile the algorithm by compiler.
  Space complexity means space neede to execute the algoritham.
  These is the basic definations which I learnt in previous semester.
• 

  slashfear

  Hi Scorpion,
  
  
  Click on the following link:
  
  #-Link-Snipped-#
  
  
  and you will get the answers...........;-)
  
  
  PS: I am not that good in algorithms pal 😒
  
  Hope this Helps you buddy!!!!!;-)
  
  -Arvind(slashfear)
• 

  pradeep_agrawal

  RajdeepCE

  Time complexity it means the time taken to compile the algorithm by compiler.

  I would not agree with this. The time complexity is not the time taken to compile the program. Its associated with the time taken for execution of the algorithm. For details read below.
  
  
  1. What's meant by time complexity and space complexity?
  
  Time Complexity:
  A program takes some input, process the input and gives some output. The total time of execution of the program may change based on the change in size or value of the input, e.g.,
  - Sorting an array of size 10 will take less time then sorting an array of size 100.
  - Finding if 7 is a prime number will take less time then finding if 31 is a prime number.
  
  The pattern with which the execution time changes for a program/algoritm defines the time complexity of the program/algorithm. This will be more clear with explanation for point 2.
  
  
  Space Complexity:
  A program takes some input, process the input and gives some output. The space (or say memory) used during execution of the program may change based on the change in size or value of the input. The pattern with which the space usage changes for a program/algoritm defines the space complexity of the program/algorithm. For example,
  
  Consider a matrix of order nXn such that
  element at [i,j] = 0 for i != j
  element at [i,j] != 0 for i = j
  
  User can represents the matrix as:
  - A 2D array matrix[n,n], where value of each element is stored in the array. As the size of matrix grow the space required will also grow with factor nXn.
  - A 1D array matrix[n], where we specify matrix = element at [i,j] for i = j because we know that all other elements are 0. As the size of matrix grow the space required will also grow with factor n, and hence will need less space.
  
  
  
  2. What do you mean when you tell a particular program is order(n) or order(n^2) etc?? How to find the order of a given program?
  
  To explain this consider below algorithms.
  
  Algorithm 1: Determine if a number is divisible by 2 or not
  The code for this will look like
  

  int n = ;
  if(n % 2) {
    printf("Number is not divisible by 2");
  } else {
    printf("Number is divisible by 2");
  }
  

  Whatever is the value of 'n', the program will take a constant time. So the complexity or order of the algorithm is O(1).
  
  
  Algorithm 2: Linear search in an array of size n
  The sample code for this will look like
  

  int arr[n] = ;
  int num = ;
  int i = 0;
  for(i = 0; i < n; i++) {
    if(arr[i] == num) {
      break;
    }
  }
  if(i == n) {
    printf("Number not found");
  } else {
    printf("Number fount at %d", i);
  }
  

  - The statement given under for loop takes some constant time.
  - The execution time will be determined by the number of times the for loop gets executed.
  - For a given n elements the for loop will execute maximum number of times when the element is not present in the list (will execute for n times in that case).
  - With increase in value of 'n' the number of times the for loop will execution will also increase, e.g., for (n+5) elements the loop will execute maximum (n+5 )times.
  - The execution time increases linearly with increase in value of n. Hence the order of algorithm is O(n).
  
  
  Algorithm 3: Sorting an array of size n
  The sample code for this will look like
  

  int arr[n] = ;
  for(int i = 0; i < n; i++) {
    for(int j = (i + 1); j < n; j++) {
      if(arr[i] > arr[j]) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  

  - The statement given under inner for loop takes some constant time.
  - The execution time will be determined by the number of times the inner statement gets executed (or say both for loop gets executed).
  - The for loop[ of i will get executed from 0 to (n-1)
  For i = 0, j will get executed from 1 to (n-1), i.e., (n-1) times
  For i = 1, j will get executed from 2 to (n-1), i.e., (n-2) times
  .
  .
  .
  For i = (n-2), j will get executed from (n-1) to (n-1), i.e., 1 times
  For i = (n-1), j will get executed from n to (n-1), i.e., 0 times
  - Total number the loops (or inner statements) gets executed is
  0 + 1 + ... + (n-2) + (n-1)
  = (n-1)(n-1 + 1)/2 //using formula that sum of number from 1 to n is n(n + 1)/2
  = n(n-1)/2
  = (n^2 - n)/2
  - Hence with increase in size of n the execution time will change by (n^2 - n)/2.
  - In expression the most effect is due to highest order, which in case of (n^2 - n)/2 is n^2. Hence we ignore others and say that the order of algorithm is O(n^2).
  
  
  3. How to find if a given program's order can be reduced or not?
  Ahhh, this is a tough question to answer. I feel there is no fix technique to determine if the algorithm can be optimized or not, or if a more optimized algorithm is possible to solve a given problem. This is more driven by logic.
  
  
  Let me know if any section need more explanation or if i need to cover more algorithms with different complexities.
  
  -Pradeep
• 

  silverscorpion

  @ Slashfear: Thanks for the link. It was very good.
  
  @ Pradeep: Thanks very much for the detailed and clear answer. The doubts are clear now.
• 

  slashfear

  @Pradeep, Good explanation buddy 😁
• 

  Corpse-Thrust

  Wow, awesome stuff Pradeep. That stuff helped me a lot in my viva. Thank god I checked the forums before going to the practicals 😛
  
  I guess I should hang around here more often... 😎
• 

  pradeep_agrawal

  @ silverscorpion, slashfear, Corpse-Thrust
  
  Thanks for your appreciation buddy.
  
  -Pradeep
• 

  Kaustubh Katdare

  No doubt, we've awesome engineers on CE. @ Corpse - Thrust : Tell your friends about CE too. 😀
• 

  shalini_goel14

  pradeep_agrawal

  @ silverscorpion, slashfear, Corpse-Thrust
  
  Thanks for your appreciation buddy.
  
  -Pradeep

  Hello Pradeep Sir,
  I also appreciated your work 😔, just try to give a look here outside of Computer Science section also 😁
  
  #-Link-Snipped-#