-1

I'm studying for an exam and I can't seem to understand data structures & algorithm complexity i.e. I know that a linked-list has insert, get , delete method implementation, but what I cannot understand about it is 0(n) or 0(1).
I know that n means list size and 1 means linear but I don't understand the 0 or O. If you can explain what complexity is and how it works I'd be grateful. So if you could please help me. Thank you.

TheJavaFan
  • 341
  • 3
  • 15
Imtanan Raja
  • 21
  • 4
  • @StackFlowed Thanks for your help cos it was it abit tricky for me – Imtanan Raja Apr 17 '15 at 20:08
  • Lets start with the most import thing it's called 'big o notation' - just to let you know what you have to google for. The [wikipedia article][1] might give you a pretty good overview what it's all about. If you're in a rush or you just want to double check if you got everything right you might have a look at this [cheatsheet][2] [1]: http://en.wikipedia.org/wiki/Big_O_notation [2]: http://bigocheatsheet.com/ – TobiSH Apr 17 '15 at 20:10
  • Your example: O(1) means constant. According to your example the complexity will not change if you add one element to a linked list with 5 elements or 5000 elements O(n) means linear complexity. According to your example the complexity of a get operation of a linked list will increase linear with the size of the list. – TobiSH Apr 17 '15 at 20:10

1 Answers1

1

O(n) or O(1) stands for the order of complexity. For example, if you want to search an element in a array of length n, and you are using linear search(means start searching from first element one by one) then obviously searching time depends on the size of array. So linear search has O(n) complexity. Whereas take an example of searching in hashmap. In hashmap insertion and searching are done on basis of hashing algorithm. Means for every search time taken to search will not depend on size of hashmap, but will be a constant time taken by hashing algorithm. So this will be O(1) complexity. Hope this will help to understand.

Rahul
  • 309
  • 1
  • 11