what is the space complexity of the program ?

• can anyone tel me how shud i prepare for technical ques in wipro interview.. pls help me
  
• 9 years agoHelpfull: Yes(12) No(3)
• First time complexity... lets say you have an algorithm that takes n elements and it takes about n^2 steps to complete the algorithm. This gives time complexity O(n^2), and that means it takes a lot more time, if you increase the number of elements n. For some algorithm that is O(log n), the algorithms will stay relatively fast even for large number n. The O(n^2) does not mean exactly n^2 operations, but it means the class of complexity... it can be any function that falls into:
  constant*n^2 + any function that is strictly smaller than n^2 + constant.
  
  You can calculate your class by measuring time for several element counts n, and then solving the equation bellow for some measurements, and calculation if it fits the other measurements (the ones you didn't use in equation) close enough:
  Time(n) = k*n + c (for testing O(n))
  Time(n) = k*n^2 + c (for testing O(n^2))
  Time(n) = k*log(n) + c (for testing O(log(n)))
  etc.
  but this is very time consuming and outside university noone does it like this.
  
  it's usually better to just analyze the code:
  looping through a table is O(n)
  but nested loops through a table is O(n^2)
  operations in trees usually have O(log n)
  sorting can be done in O(n*log n)
  recursive-split algorithms (like quick-sort, or binary sort) are usually O(n^2) or O(log n) (check the master theorem if you want to have equation for this)
  hard problems like traveling salesmen are exponential O(2^n)
  doing something simple not related to the element count is O(1)
  etc.
  
  For space complexity it means how much extra memory the algorithm takes...
  if you do all calculation inside the original data structure this complexity is O(1)
  if you must make a copy of the structure it's O(n)
  etc.
• 9 years agoHelpfull: Yes(5) No(5)
• space complexity is nothing that is the space utilized by program while running
• 9 years agoHelpfull: Yes(4) No(0)
• Space complexity is a measure of the amount of working storage an algorithm needs.
• 9 years agoHelpfull: Yes(2) No(1)
• space complexity of any program can be defined as the amount occupied by any program in memory....
• 8 years agoHelpfull: Yes(1) No(0)
• space complexity is the amount of working storage the algorithm needs.
• 7 years agoHelpfull: Yes(1) No(0)