retagged by
2,185 views
2 votes
2 votes

An ideal sort is an in-place-sort whose additional space requirement is

  1. O (log$_2$ n)
  2. O (nlog$_2$ n)
  3. O (1)
  4. O (n)
retagged by

3 Answers

1 votes
1 votes
An ideal sort is an in-place-sort whose additional space requirement is log n for function call.

A is answer
1 votes
1 votes

In its strictest form, the algorithm can only have a constant amount of extra space, counting everything including function calls and pointers. However, this form is very limited as simply having an index to a length n array requires O(log n) bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though non-constant extra space for its operation. Usually, this space is O(log n). 

Source : https://en.wikipedia.org/wiki/In-place_algorithm

0 votes
0 votes
space complexity for any algo is =input+extra .......and this extra generally depends on inplace or outplace nature....if inplace than extra is stack space i.e log n.............so option A
Answer:

Related questions

3 votes
3 votes
1 answer
1
go_editor asked Aug 8, 2016
3,013 views
The number of disk pages access in B-tree search, where h is height, n is the number of keys and t is the minimum degree, is$\theta (\log_n h*t)$$\theta (\log_t n*h)$$\th...
1 votes
1 votes
2 answers
3