-5

Suppose :

int arr[10]; // you have O(n ) linear algorithm for search

but when you use :

std::vector<int> V;

Question is : What's Algorithm complexity for searching behind of impelentation of vector?

Martin Törnwall
  • 9,299
  • 2
  • 28
  • 35
PersianGulf
  • 2,845
  • 6
  • 47
  • 67
  • `std::vector` has constant time random access, so it's the same. – kec Dec 20 '14 at 03:23
  • possible duplicate of [std::vector versus std::array in C++](http://stackoverflow.com/questions/4424579/stdvector-versus-stdarray-in-c) – Dinal24 Dec 20 '14 at 03:32

1 Answers1

2

Searching in an array and std::vector is O( n ) not O( log n )

O( log n ) will be achieved only when array/std::vector is sorted.

std::vector implementation doesn't include any searching algorithm, however to get O( log n ) you first need to sort it and then perform binary search, this is same as with an array too.

P0W
  • 46,614
  • 9
  • 72
  • 119
  • @MohsenPahlevanzadeh I don't think I need to update my post, IMHO you have pretty much changed your entire question now, anyway, for performing a search in `std::vector` you can use [_`std::find`_](http://en.cppreference.com/w/cpp/algorithm/find) – P0W Dec 20 '14 at 06:11