0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Have you thought about what happens when you implement quick sort or merge sort for linked lists? $\endgroup$ – adrianN Sep 17 '16 at 14:15
  • $\begingroup$ @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) $\endgroup$ – Saravanan Sep 17 '16 at 15:06
  • 1
    $\begingroup$ 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. $\endgroup$ – adrianN Sep 17 '16 at 15:08
  • $\begingroup$ yeah sure, but what about other algorithms ? Is that true for all other $\endgroup$ – Saravanan Sep 17 '16 at 15:12
  • 1
    $\begingroup$ 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. $\endgroup$ – adrianN Sep 17 '16 at 15:20
1
$\begingroup$

Note that complexity classes are classes of problems, not classes of algorithms. Specifically, complexity classes are classes of problems that can be solved within particular resource bounds by some algorithm. So, for example, sorting is in polynomial time because there is at least one algorithm that sorts with this resource bound. (In fact, you probably know many algorithms that do this.)

When it comes to comparing different algorithms for solving the same problem, yes, they may have different resource usage. The fact that you have random access to the elements of an array but not to a linked list means that you can probably design more efficient algorithms based on arrays compared to those based on linked lists. And note that, by using different data structures, they are different algorithms: they involve different computational steps.

Note also that all of this is dependent on your model of computation. For example, if you're solving computational problems using Turing machines, then arrays and linked lists are essentially the same thing, because we can only access the array by moving the tape head sequentially through the elements. Typically, though, when analyzing actual algorithms, we use models of computation, such as the random access Turing machine, that correspond more closely to actual computers.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Saravanan Sep 18 '16 at 4:54
  • $\begingroup$ @saravanan I answer that in the second paragraph. $\endgroup$ – David Richerby Sep 18 '16 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.