can someone noobishly splain to me the O(1), O(N), O(N^2) and O(log N)

[koloastreet]

like a map vs array vs stack?

if not, anyone know of an easy read somewhere online?

thanks...

oh its for a possible interview coming up this week and its been 5 yrs since i cracked open a CS book. stupid me....

 

[smack Down]

A stack and an Array are based on the same data structore so all operations take the same amount of time. A stack is a limited interface to an array. A map is a real general data structor and be back by anything so its insertion/search could degrade to that of an array.

 

[tfinch2]

http://en.wikipedia.org/wiki/Big_O_notation

 

[koloastreet]

? O(1): Pronounced ?order 1? and denoting a function that runs in constant time
? O(N): Pronounced ?order N? and denoting a function that runs in linear time
? O(N2): Pronounced ?order N squared? and denoting a function that runs in quadratic time
? O(log N): Pronounced ?order log N? and denoting a function that runs in logarithmic time
? O(N log N): Pronounced ?order N log N? and denoting a function that runs in time proportional
to the size of the problem and the logarithmic time
? O(N!): Pronounced ?order N factorial? and denoting a function that runs in factorial time

what does the time factor mean?

 

[tweakmm]

The only big O you need to worry about.

:thumbsup:

I'd actually explain big o notation if I didn't have to go to work. :laugh:

 

[Jmman]

The Big O stands for Overstock.com....oh sorry, you are talking about program efficiency.....

 

[koloastreet]

like what is constant, linear, quadratic, logarithmic time interms of searching for a particular value in lets say an array using a brute force method like bubble sort?



for example if a program takes 10 seconds to search through 10 items, and it takes 20 seconds to search through 20 items, that is said to run in constant time?

 

[statik213]

Originally posted by: koloastreet
like a map vs array vs stack?

if not, anyone know of an easy read somewhere online?

thanks...

oh its for a possible interview coming up this week and its been 5 yrs since i cracked open a CS book. stupid me....

it depends a lot on the underlying implementation of each data structure.

An array is easy, looking up a random element by index is O(1) -- looking at all the elements in order is O(n).
If th array is sorted you can search for an element in O(log n) time using binary search.
Note: "search" and "look up" are different -- think of the meaning.

A linked list, take O(n) time to look up a random element (by index/position). if it is a sorted linked list, it still takes O(n) time to search for an element.

A stack can be implemented wiht a linked list OR an array or in other ways (?).
A stack "needs" to have quick pop/push operations and these are O(1) for both array and linked list based stacks.

Maps/Hashtables are pretty complicated, you need to know a LOT about the underlying implementation before you can answer these questsion.
BUt in general, you should expect to have O(log n) look up a value by key, where n is the size of the map -- not the number of (key, values) in the map. Maps usually have some amount of unused/wasted space in them.
A map could be implemented naively using a linked list, this will give you O(n) performance for just about everything -- so the implementation IS important.

 

[statik213]

Originally posted by: koloastreet
like what is constant, linear, quadratic, logarithmic time interms of searching for a particular value in lets say an array using a brute force method like bubble sort?



for example if a program takes 10 seconds to search through 10 items, and it takes 20 seconds to search through 20 items, that is said to run in constant time?

That would be linear time my friend. Constant time would be running in 1 second, with 10, 20 or 10000000000000000000 items.

Edit: You said "search through 10 items", do you mean search FOR 10 items or search a list of 10 items? YOu were right if it was the later.

 

[koloastreet]

a list of 10 items....so for a constant time, if the list is 20 items, it still would take 10 seconds? or does time increase proportionately to the size of the list? and thats said to be constant?

wait im confused.... crap...

Originally posted by: statik213

Originally posted by: koloastreet
like what is constant, linear, quadratic, logarithmic time interms of searching for a particular value in lets say an array using a brute force method like bubble sort?



for example if a program takes 10 seconds to search through 10 items, and it takes 20 seconds to search through 20 items, that is said to run in constant time?

That would be linear time my friend. Constant time would be running in 1 second, with 10, 20 or 10000000000000000000 items.

Edit: You said "search through 10 items", do you mean search FOR 10 items or search a list of 10 items? YOu were right if it was the later.

 

[hypn0tik]

If you consider a plot of time vs. # of elements, and look at it's shape, you'll be able to tell by the shape what the order is.

Plot the numbers in your example and you'll see that it gives you a line. Hence, that operation is linear and is O(N).

 

[Cattlegod]

take this for example: you have two algorithms A and B

A takes 1 second to complete 1 item
B takes 1 second to complete 1 item

then

A takes 20 seconds to complete 20 items
B takes 400 seconds to complete 20 items

A is O(n)
B is O(n^2)