• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

What is the Big O of my code and why?

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My guess is O(n^2), because for every n i iterate the String once again, but i'm not sure.

 
Saloon Keeper
Posts: 10428
223
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First, it can't be O(n^2) because n is not defined. Let's define it first: n is the length of the input string s.

Secondly, you can't just talk about the complexity class of an algorithm without specifying what cases to consider. The best case can have a radically different complexity than the worst case. The worst case is where the entire input consists of no more than k distinct characters. The best case is when the input consists entirely of distinct characters.

Let's consider the worst case first. We take an input string s = "ababa" and k = 2 , because your algorithm does not work correctly for s = "aaaaa". The variable k doesn't play a role, because the number of distinct characters is never greater than k. The outer loop will always consider each character of s once. For every iteration of the outer loop, the inner loop will run one iteration fewer. That means for input "ababa" it will run 5 times, then 4 times, then 3 times, then 2 times, then 1 time. This series can be calculated quickly with the formula f(n, k) = n*(n+1)/2. Because in complexity classes, we don't consider constant factors, f ∈ O(n^2).

The best case is when every character is distinct. That means the inner loop will never run more than k times. That means the upper bound g ∈ O(n * min(n, k)).
 
Saloon Keeper
Posts: 3415
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That "worst case" is easy to fix. With "string.chars().distinct().count()' you determine the number of distinct characters. If that is <= k, you can return the string itself.

Another way, a bit more complex but it saves you from rebuilding the substring and Set from scratch each time you change your x, is to maintain a Map<Character, Integer>, that you use as a frequencymap.
Initially, fill it with characters from the string until you have the maximum index for which the substring has K distinct characters. Then, starting from the first character of the string, reduce its frequency, until the frequency of the char at hand becomes 0. Remove that character from the map. map.size() will be K - 1. Then, starting from that max index + 1, add characters to the map until you reach the max K again. Et cetera.

As said, a bit more complex, but by maintaining the startindex and that max index you do not need to maintain that substring. A method that is very handy for all this, is the Map methiod: computeIfAbsent. See the API of Map.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!