NO CODING JUST EXPLANATIONS 1) Counting total number characters that have a dupl
ID: 3697155 • Letter: N
Question
NO CODING JUST EXPLANATIONS
1) Counting total number characters that have a duplicate within a string (i.e. "gigi the gato" would result in 7 (g x 3 + i x 2 + t x 2)
For the problem segment above, do the following:
- Create an algorithm(PSEUDOCODE) to solve the problem
- Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor.
- Identify the operations that must be counted. You need not count every statement separately. If a group of statements always executes together, treat the group as a single unit. If a method is called, and you do not know the running time of that method, count it as a single operation.
- Count the operations performed by the algorithm or code. Express the count as a function of the factors you identified in Step 2. If the count cannot be expressed as a simple function of those factors, define the bounds that can be placed on the count:the best case (lower bound) and worst case (upper bound).
- Determine what the Best Case Inputs are, and the Worst Case Inputs are, and the efficiency of your implementation
- Transform your count formula into big-O notation by:
- Taking the efficiency with worst case input
- Dropping insignificant terms.
- Dropping constant coefficients.
Explanation / Answer
Lets assume that : given string has only lower alphabate letter
Step 1: create a count array of size 26(there are 26 alphabate).
Initialize each entry with zero.
First entry for 'a', 2nd for 'b'..so on
Step 2:
Iterate through each character of given string and increment corresponding entry
of count array
Step 3: Initialize result with zero
Step 4: Iterate over count array. If entry of count array is grater than one, then add value of current element
of count array to result
Step 5: print result
Time Complexity:
Step 1: O(1)
Step 2: O(n) : n is number od character in given string
Step 3: O(1)
Step 4: O(1) : only 26 entry constant time
So, overall time complexity: O(n).
Best case, Averag Case and Worst case: all are same => O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.