[Show all top banners]

wai_wai
Replies to this thread:

More by wai_wai
What people are reading
Subscribers
:: Subscribe
Back to: Kurakani General Refresh page to view new replies
 How do you sort a Linked List (singly connected) in O(n)
[VIEWED 8624 TIMES]
SAVE! for ease of future access.
Posted on 01-28-10 1:16 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 


How do you sort a Linked List (singly connected) in O(n)?




 
Posted on 01-28-10 2:33 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

This is not a place to post assignment. I am sick of people posting their assignment and hoping someone to answer it. No one's gonna solve your problem while you're in a job interview. Study hard keeping that in mind. This thing will only make you lazy and degrade your learning habbit. Try to learn from books and google it yourself. I'm sure there must be hundreds of solutions for this in google as this is a pretty popular problem.
 
Posted on 01-28-10 4:22 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

FYI..this is not an assignment and I am not a college guy. I know how to sort in O(n^2) andO(nlogn), Just didn't know how to sort in O(n) and thought somebody could help me here in sajha..!!
If u don't know anything....just keep quite..I posted this question assuming somebody will provide the algorithms steps and we can discuss on it...didn't know moron like you would come in between!!

 
Posted on 01-28-10 4:26 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

I don't know the answer to your question. But the way this thread is headed, you might enjoy the following.
http://forums.sun.com/thread.jspa?threadID=565098&start=0
Last edited: 28-Jan-10 04:26 PM

 
Posted on 01-28-10 4:49 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

No, you can not sort in O(n) time. Sorting requires comparison and reinsertion of items, so it is almost impossible to do it in O(n) time unless you are starting off with empty or already sorted array.  
 
Posted on 01-29-10 12:04 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

is O(n) worst case? if it is you might wanna try radix sort, counting sort or some other non-comparison based sorting technique.

 
Posted on 01-29-10 12:23 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

i am confused  now.   O(n) is  just a reference to time??  or is it the number of objects required??

 
Posted on 01-29-10 12:48 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

O(n) is the asymptotic upper bound of algorithm, the best case is known as big Sigma(n), and the average case is known as big Theta(n). O(n) is usually considered as it represents the worst case of an algorithm. There are notation such as small o(n) and small omega(n) which are upper and lower case but are not asymptotically bounded. 
In the simplest word, O(n) is the worst case running time of an algorithm. 

Most of the non comparison based sorting techniques are either unstable or assume that the number of items to be sorted is much less than 2^k (k is the size of each key). Counting sort is exponential in runtime cost in worst case. The only sorting algorithm that is stable and can be implemented fairly easily is LSD radix sort, but getting n much less than 2^k is very hard. (See wikipedia)

 
Posted on 01-29-10 1:10 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

I think here is a confusion
I was referring O(n) as Computational complexity.

O(n) is not the worst case running time.
The complexity order is { O(n^2), O(nlogn), O(n),  O(logn)}  worst case to best case respectively.

See the Order here



 
Posted on 01-29-10 1:23 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

My answer for a simple explanation for big O notation was for 1987 AD. 

Wai_wai,
 Computational complexity is measured either in running time or memory usage. If you read further in the link you have provided, it clearly says that big O only provides upper bound. Sorry, if I am making it confusing here, but whatever I wrote in my previous post is true. Big O(n) only gives the upper bound. 

Here is an open courseware from MIT that describe everything about algorithm complexities. http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm

Good luck. 

 
Posted on 01-29-10 3:32 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

hmmm.. still confuses  me,  but  what worries me is that i am a cs major and i have never heard about these  logarithmic terms before.  i know i have to  take  some  more  classes related to  logarithms,  but just so that i get an idea,  at what level do we need to know all these?

i am technically 3rd year (recently transferred), but from looking at my required classes, it will still take  me about 3 more to graduate.(BSc in CS)

 
Posted on 01-29-10 3:33 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

i do understand the assymptotic behaviour and all, but from the  maths classes i have taken, so i am guessing the term means the same.

 
Posted on 01-29-10 10:35 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/6_046J-2005-L02.pdf

1987 AD, hope the above link will provide a clear understanding about some asymptotic notations. 

 
Posted on 01-29-10 10:59 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

, @ Gajedi: O(n) doesn't always mean worst-case its just the upper bound. Worst case means what is the maximum running time the sorting algorithm can take if the input is arranged in the worst order for that particular algorithm. For example, look at the table in http://en.wikipedia.org/wiki/Sorting_algorithm

@1987 AD: I studied this in my "Data Structures and Algorithms" class. It was a 300-level course @ my univ where courses are upto 400-level max in undergrad. It is very important for programming and other applications. The saying goes like, " You can either program for 10 years and be a good programmer, or your can take an alogrithms class and be one in 3 :)"


 
Posted on 01-29-10 11:37 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

Sarkar123,
  First and foremost, wikipedia is not a credible source. Read my previous reply about O and other notations. O is the upper bound which in fact defines the worst case behavior of an algorithm. 
If you read the book "Introduction to Algorithm" and specially "Growth of functions", you will understand the concept clearly. The growth of a function is defined in terms of big Omega, Theta, and O notation (if tightly bound) which are nothing less than best, average, and worst case running time of an algorithm.  



 
Posted on 01-29-10 12:52 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

@Gajedi: Notations (sigma, O, theta)  and cases (worst, average, best) are different things.

http://lcm.csa.iisc.ernet.in/dsa/node9.html

http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

@wai wai: I think the sorting you wanna do is Bucket sort. Though I am not very familiar with that one!

 
Posted on 01-29-10 3:15 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

http://www.cs.cmu.edu/~pattis/15-1XX/15-200/lectures/listprocessing/index.html


 
Posted on 01-30-10 12:53 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

Sarkar, Are you sure they are different than the notations? Please read the whole thing in the link you have provided and not just one page talking about big O. 
 
Posted on 01-30-10 9:36 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

@Wai_Wai
What type of value does the List contains. If it's an integer then what will be the range??
As someone previously suggested, the sorting algorithm will depend on the type of value in the List.

There are couple of options:
1. Use a Heap (min heap). First insert all, then remove one by one. -- o(nlogn)
2. Use a lookup array. i.e. something like bucket sort. O(n + m) where n is the size of the list and m is the size of the lookup array
3. Insert all and remove all from a BST. -- O(nlogn)

For the requirement of O(n) I would rather go for bucket sort like algorithm:
First determine the range of values in the list.
And sort it based on the value or alternatively create a new List with those values.


 
Posted on 01-30-10 10:10 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

@ Gajedi: They might look alike but they are different. Big-O doesn't HAVE to be a worst case. How would you then explain the best case running time of an insertion sort to be O(n), average case to be O(n2) and worst case be O(n2)? A worst case running time could have a Theta(n) or a Omega(n) notation (sorry in the previous thread I wrote sigma for omega). It all depends. Normally for sorting we use big-O in ALL cases (be it worst, average or best). But for other things, for eg. the worst case running time of inserting or finding a key in a hash table is always Theta(n).

I have the following lecture from UCBerkeley that might make it clear for you. The link to this lecture is http://www.eecs.berkeley.edu/~jrs/61b/lec/21 . Scroll down the paragraph before the title "ALGORITHMIC ANALYSIS"

"Remember that the choice of O, Omega, or Theta is _independent_ of whether
we're talking about worst-case running time, best-case running time,
average-case running time, memory use, annual beer consumption as a function of
population, or some other function. The function has to be specified.
"Big-Oh" is NOT a synonym for "worst-case running time," and Omega is not a
synonym for "best-case running time."





 


Please Log in! to be able to reply! If you don't have a login, please register here.

YOU CAN ALSO



IN ORDER TO POST!




Within last 200 days
Recommended Popular Threads Controvertial Threads
शीर्षक जे पनि हुन सक्छ।
NRN card pros and cons?
What are your first memories of when Nepal Television Began?
TPS Re-registration
Democrats are so sure Trump will win
is Rato Bangala school cheating?
Basnet or Basnyat ??
nrn citizenship
Sajha has turned into MAGATs nest
Nas and The Bokas: Coming to a Night Club near you
डलराँ कमाएर ने .रु मा उडांउदा !@#
ChatSansar.com Naya Nepal Chat
डीभी परेन भने खुसि हुनु होस् ! अमेरिकामाधेरै का श्रीमती अर्कैसँग पोइला गएका छन् !
3 most corrupt politicians in the world
भर्खरै मात्र नम्रता श्रेष्ठले सारूक ताम्राकारका बारे आफ्नो मुख खोले
if you are in USA illegally and ask for asylum it is legal
Returning to Nepal with us citizenship. Property ownership
Top 10 Anti-vaxxers Who Got Owned by COVID
आज बाट तिहारको सेल सकियो
निगुरो थाहा छ ??
Nas and The Bokas: Coming to a Night Club near you
Mr. Dipak Gyawali-ji Talk is Cheap. US sends $ 200 million to Nepal every year.
Harvard Nepali Students Association Blame Israel for hamas terrorist attacks
TPS Update : Jajarkot earthquake
is Rato Bangala school cheating?
NOTE: The opinions here represent the opinions of the individual posters, and not of Sajha.com. It is not possible for sajha.com to monitor all the postings, since sajha.com merely seeks to provide a cyber location for discussing ideas and concerns related to Nepal and the Nepalis. Please send an email to admin@sajha.com using a valid email address if you want any posting to be considered for deletion. Your request will be handled on a one to one basis. Sajha.com is a service please don't abuse it. - Thanks.

Sajha.com Privacy Policy

Like us in Facebook!

↑ Back to Top
free counters