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
$\begingroup$
$\endgroup$
8
-
1$\begingroup$ Have you thought about what happens when you implement quick sort or merge sort for linked lists? $\endgroup$– adrianNSep 17, 2016 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$– SaravananSep 17, 2016 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$– adrianNSep 17, 2016 at 15:08
-
$\begingroup$ yeah sure, but what about other algorithms ? Is that true for all other $\endgroup$– SaravananSep 17, 2016 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$– adrianNSep 17, 2016 at 15:20
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Sep 17, 2016 at 21:11
-
$\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$ Sep 18, 2016 at 4:54
-
$\begingroup$ @saravanan I answer that in the second paragraph. $\endgroup$ Sep 18, 2016 at 8:18