CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Quavo
Quavo

Reputation: 11

What is it meant by that implementation in different programming languages may impact the time complexity?

I always thought that the time complexity using Big O will be the same for some logic of code for any programming language, but I have been reading how pass by reference or pass by value in C++ or other features in other languages may sometimes have a different impact in the time complexity. Is this what is meant by saying that implementation in different programming languages may impact the time complexity? How can one be able to see such differences.

Upvotes: 1

Views: 100

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59174

No matter what, you can write the same algorithm in any (realistic) programming language and get the same time complexity.

But the "normal", "usual", or "obvious" way of writing things in different languages might produce implementations with different complexity.

Passing by reference vs value isn't usually in that category, since both are natural in languages that let you choose, and languages that don't let you choose pass by reference in those cases.

Some examples could be:

  • Slicing a list in one language might make a copy in O(N), while in another it might return a reference to the sublist O(1)
  • A map or set in one language might be implemented in a hash table (expected O(1)/op), while in another it might be a BST (O(log N)/op)
  • Different languages have different optimizations built in for repeated string or list concatenation.

In all of these cases, you can get the best complexity by implementing your own data structures or doing things in a particular way, but that's not what programmers would usually do.

Upvotes: 5

Andreas
Andreas

Reputation: 159086

Lets say your algorithm takes a string as parameter, and that n is the length of that string.

If the algorithm then loops n times and calls a method inside the loop, passing the string as a parameter to the method, there are two possible Big-O's.

For the purpose of this example, the method itself is O(1), i.e. it doesn't doing anything that is related to the string length. E.g. it could be the equivalent of charAt(String str, int index).

  1. Pass by reference: Since only a reference to the string is passed to the method, the total cost of the method invocation is O(1), so the overall cost the algorithm is O(n).

  2. Pass by value: Since calling the method requires copying the string itself, the cost of the method invocation is O(n), making the overall cost the algorithm O(n2).

As you can see, the parameter passing methodology affects the Big-O of the entire algorithm.

Some languages, like Java passes references by value, i.e. it never passes objects by value. Other languages can pass by reference (e.g. a C++ pointer to the object), or by value (e.g. C++ passes struct objects by value).

Upvotes: 3

Related Questions