# Given an algorithm, do worst case time complexity “class” vary with array and linked list?

My intuition says that I can make a sorting algorithm(may be a strange, not an useful), such that with array it have different worst case time complexity class and linked list(assuming time complexity of operation performed in linked list are same as conventionally used) with different complexity class.
But what about the sorting algorithms which are conventionally used(may be the algorithms in CLRS)?
I am assuming the implementation done on RAM model and by class I mean the set $\theta(f)$ with f as worst case running time of the algorithm

• Have you thought about what happens when you implement quick sort or merge sort for linked lists? – adrianN Sep 17 '16 at 14:15
• @adrianN Yeah practically it does make different, but what about complexity class? quick sort is in $\theta (nˆ{2})$ in both and merge sort in $\theta(nlog(n))$ in both(worst case) – Saravanan Sep 17 '16 at 15:06
• I'd argue that you can implement both sorting algorithms for linked lists with the same asymptotic bounds. I suggest you try to figure out how, it shouldn't be terribly difficult. – adrianN Sep 17 '16 at 15:08
• yeah sure, but what about other algorithms ? Is that true for all other – Saravanan Sep 17 '16 at 15:12
• No, for example the algorithm that takes a list (or an array) and a number $k$ and returns the $k$-th element has a different runtime. – adrianN Sep 17 '16 at 15:20

• May be, I might not have used technically correct terms, but My question is do they both(one for array and one for linked list) lie in the same $\theta(f)$(by class I meant this set) for some function f(using RAM model)?<br> I think now my question is precise – Saravanan Sep 18 '16 at 4:54