Win a copy of Pro Spring MVC with WebFlux: Web Development in Spring Framework 5 and Spring Boot 2 this week in the Spring forum!
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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Jeanne Boyarsky
• Liutauras Vilda
Sheriffs:
• Rob Spoor
• Bear Bibeault
• Tim Cooke
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Piet Souris
Bartenders:
• Frits Walraven
• Himai Minh

# What is the Big O of my code and why?

Greenhorn
Posts: 14
• Number of slices to send:
Optional 'thank-you' note:
My guess is O(n^2), because for every n i iterate the String once again, but i'm not sure.

Saloon Keeper
Posts: 12993
281
• 1
• Number of slices to send:
Optional 'thank-you' note:
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: 4501
166
• Number of slices to send:
Optional 'thank-you' note:
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.