This table provides information about real estates. The column “Type” contains either the value “Apartment”, “House”, “Townhouse” or “Villa”. The number of entries for each type is roughly 25% of the total number of entries in the table.
Table Name Column Name Data Type RealEstate ID DEC(10) Type VARCHAR(40) Price DEC(10,2) Size DEC(4) A typical query asks for all real estates of a given type: select ID from RealEstate where Type = ′House’ Two indexes were defined for this table. The first index was defined for the column ′ID′ and the second index was defined for the column ′Type′. what will be the time complexity of this query relative to the number of entries n and the size of the result set m??
the time complexity will be O (log(n)+m) or O(n)??
This is very roughly speaking and in a way a speculation:
The complexity should be O(m) because due to the indexes present,
the DB engine can find/locate the records matching Type = 'House'
in constant time. So all that is taking time here is to process the
matching records whose count is m (e.g. to read them and to return
them to the caller). So the complexity is O(m) because the processing
is proportional to the count of the records returned.
But when viewed at a lower level, I guess it all depends on many other things too:
if your index is well-maintained (not fragmented), if the records are well-situated
on the disk (e.g. sequentially), etc, etc. So it is hard to give a direct/simple
big O formula.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments