This paper pursues hydrological interpretation of a statistically derived index of basin complexity. We introduce an index of basin complexity based on a model of least statistical complexity that is needed to reliably model daily streamflow of a basin. Daily streamflow is modeled using k-nearest neighbor model of lagged streamflow. Such models are parameterised by the number of lags and radius of neighborhood that it uses to identify similar streamflow events from the past. These parameters need to be selected for each time step of prediction ’query’.We use 1) Tukey half-space data depth function to identify time steps corresponding to ’difficult’ queries and 2) then use Vapnik-Chervonenkis (VC) generalization theory, which trades off model performance with VC dimension (i.e. a measure of model complexity), to select parameters corresponding to k nearest neighbor model that is of appropriate complexity for modelling difficult queries. Average of selected model complexities corresponding to difficult queries are then related with 6 hydrologic characteristics of 303 MOPEX basins from eastern United States that include slope of the water retention curve, ratio of precipitation to potential evaporation, 5-week gradient of NDVI, mean slope, precipitation seasonality index and porosity. All the hydrological characteristics have been derived from the MOPEX database to represent climatic, vegetation and soil characteristics of the basins in a concise manner. Results find that drier basins are more difficult in terms of prediction of its stream flow based on historical similarity of past flow events. However faster responding basins (e.g. basins with faster responding vegetation such as those with higher gradient of NDVI or basins with steeper slopes of corresponding water retention curves) or those that have lower storage capacity (e.g. basins with lower porosity) are more complex. Finally, wetter basins that are flatter are found to be more complex. The results also suggest that basin complexity as computed can be interpreted as an index of hydrological similarity, and reaffirms prior observations that minimum complexity that is required to model a basin appears to depend on its hydrological characteristics.