Average case complexity of Algo
What is meant by average case complexity of an algorithm?
 Average of complexity of all possible complexities over different inputs, OR
 Complexity of an input which is average of all possible inputs.
According to me when we say that average case complexity of Quicksort is N log(N)
, I understand that it is for an input which is not skewed towards being already somewhat partially sorted nor being extremely unsorted. This complexity is for a random input, which (according to me) means an input which is average of all possible inputs. Hence the term average complexity.
Kindly correct me where I am wrong. And what average complexity actually means.
See also questions close to this topic

BigO of a recursive function called twice based on two variables
What will be the time complexity of this function:
public int calculate(int n, int i, int c) { if(i >= n  c <= 0) return 1; int p1 = 2 * calculate(n, i, c1); int p2 = 1 + calculate(n, i+1, c); return p1 + p2; }
The function gets called twice, one for all values of 'c' and one for all values of 'i'. Can we say that its time complexity is O(2^(n+c)) If so, is it possible to find a tighter limit?

Is there a way to run empirical times against an algorithm without including the time it takes to iterate through N items?
I'm running a time test on an algorithm for an ArrayList that I created by taking the System time before I add N items and the time after I add N items. On analysis of the code, I know the algorithms timecomplexity is O(1). However, when running these tests I get times that do not represent O(1). The times I get are below.
n=10,000 3.38 ms
n=100,000 13.43 ms
n=500,000 53.02 ms
n=1,000,000 121.2 ms
I assume this is because I am adding N items and for the loop to run through those items, it tacks on additional time as N gets bigger.
Is there a way to disinclude the time it takes to iterate through a list of N items?
Here is my algorithm to show it is definitely O(1).
public boolean addLast(E obj) { if (this.isFull()) { return false; } if (obj == null) { System.out.println("Invalid data, ignoring"); return false; } int idx; if (this.isEmpty()) { idx = this.arrRear; } else { if (this.arrRear + 1 < this.circArr.length) { idx = this.arrRear + 1; } else { idx = 0; } } this.circArr[idx] = obj; this.arrRear = idx; this.items++; this.modsMade++; return true; }

Space complexity of Partition Label Problem
A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing size of each part.
Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8]
Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
Below is my Code for the above problem:
class Solution { public List<Integer> partitionLabels(String S) { char[] st = S.toCharArray(); int k=0,c=0; List<Integer> res = new ArrayList<Integer> (); Set<Integer> visited = new HashSet<Integer> (); for(int i=0 ; i<st.length ; i++) { int idx = S.lastIndexOf(st[i]); if(visited.add(i) && idx>i && idx>k) { k = Math.max(k,idx); visited.add(k); } else if(i == k) { res.add(ic+1); c=i+1; k++; } } return res; } }
The above code works and the time complexity of the above code in O(n) since it visits each element once.
But what is the space complexity? Since I am using a Char array whose size is the same as the the String S and a Set whose Max size can be the size of the String S, is it also O(n)?

How to print the maximum sum subsequence of an array with non adjacent elements?
I've the code to find the maximum sum that can be formed with non adjacent elements of an array. How to print the elements that contributed to the sum?
def find_max_sum(arr): incl = 0 excl = 0 for i in range(len(arr)): if excl>incl: new_excl = excl else: new_excl = incl incl = excl + arr[i] excl = new_excl return (excl if excl>incl else incl)

Large Number Multiplication With Arrays
I am writing a function that will take two integers and insert them in to a character array and do multiplication on them. The idea behind is that I can take numbers and multiply them to get a result larger than 64bits. I understand that there are tons of other ways of doing this but I want to do it this way.
I am able to successfully multiply any number by a number that is of single digit i.e.
366 * 9 = 3294
However, when I do do something like
10 * 10
I get the result
10
I think this is because that I do not handle the case of properly adding the numbers together into the result array to make it a three digit number. Below is my code.
int multiply(digit *res, digit *a, int m, digit *b, int n) { // 'a' and 'b' are my numbers to add // 'm' and 'n' are the respective lengths of 'a' and 'b' int i, j, max, low; // i is the length of the sum`1 digit ad, bd, mult, carry; if (m > n) { max = m; low = n; } else { max = n; low = m; } carry = 0; for (i = 0; i < low; i++) { for (j = 0; j < max; j++) { if (j >= m) ad = 0; else ad = a[j]; if (i >= n) bd = 0; else bd = b[i]; mult = (ad * bd) + carry; if (mult < 10) carry = 0; if (mult > 10) { carry = mult / 10; mult = mult % 10; } res[j] = mult; } } if (carry != 0) { res[j] = carry; j++; } return j; }
Does anyone have suggestions on how to handle this case upon adding into the result array? Below I have code as well that works for adding any size numbers numbers together
int add(digit *res, digit *a, int m, digit *b, int n) { // 'a' and 'b' are my numbers to add // 'm' and 'n' are the respective lengths of 'a' and 'b' int i, max; // i is the length of the sum`1 digit ad, bd, sum, carry; if (m > n) { max = m; } else { max = n; } carry = 0; for (i = 0; i < max; i++) { if (i >= m) ad = 0; else ad = a[i]; if (i >= n) bd = 0; else bd = b[i]; sum = ad + bd + carry; // what is the biggest sum can be? if (sum >= 10) { sum = sum  10; carry = 1; } else carry = 0; res[i] = sum; } if (carry == 1) { res[i] = carry; i++; } return i; }

I need help troubleshooting my code for MergeSort and Merge
So I've been working on MergeSort for an Algorithm project, but I've ran into various problems when it comes to getting the code to sort the arrays. Whenever I generate a string and put it into MergeSort, it seems to just come out exactly the same. I want some help in finding where the mistake in my code is, why is it giving me this, and a solution with a simple, but good explanation.
Here's what I've tried in the past:
 I've tried to use return arr[0] instead of arr, but it throws me an error with it being unable to convert from int to int[].
 I've looked in my merge class and everything seems to be ok there.
 I've discussed the issue with my teacher and he says that everything looks fine, but I know that there must be something wrong somewhere.
 I've tried to remove return merge(arr1, arr2) but the system throws an error telling me I have to return something.
 I've tried to print out the arrays individually, but it still shows no changes and is the exact same as the original string.
Merge method:
private static int[] merge(int[] a, int[] b) { int[] c = new int[a.length + b.length]; int counterA = 0; int counterB = 0; int counterC = 0; while(counterA != a.length && counterB != b.length) { if(a[counterA] < b[counterB]) { c[counterC] = a[counterA]; counterA++; counterC++; } else { c[counterC] = b[counterB]; counterB++; counterC++; } } while(counterB == b.length && counterA != a.length) { c[counterC] = a[counterA]; counterA++; counterC++; } while(counterA == a.length && counterB != b.length) { c[counterC] = b[counterB]; counterB++; counterC++; } return c; }
MergeSort method:
public static int[] mergeSort(int[] arr) { if(arr.length == 1) { return arr[0]; } int[] arr1 = new int[arr.length / 2]; int[] arr2 = new int[arr.length  arr1.length]; for(int i = 0; i < arr1.length; i++) { arr1[i] = arr[i]; } for(int i = 0; i < arr2.length; i++) { arr2[i] = arr[i + arr1.length]; } arr1 = mergeSort(arr1); arr2 = mergeSort(arr2); return merge(arr1, arr2); }
Because the array is randomly generated, an example would be this: 9, 1, 7, 5, 7, 2, 2, 9, 8, 9
The intended result should be this: 1, 2, 2, 5, 7, 7, 8, 9, 9, 9
However, this is what the output is instead: 9, 1, 7, 5, 7, 2, 2, 9, 8, 9 (The array comes out unchanged)