c++ - Comparison of two common comparison algorithms and their Big O help please -

today professor gave 2 take home questions practice upcoming array unit in c , wondering sorting algorithm these 2 problems resemble , big o is. now, not coming here expecting answers , have already solved them, not confident in answers post them udner each question , if wrong, please correct me , explain error in thinking.

question 1:

if decide go through array's(box) element(folders) 1 @ time. starting @ first element , comparing next. if same comparison ends, if both not equal moves on comparing next 2 elements [2] , [3]. process repeated , stop once last 2 elements compared , note array sorted last name , looking same first name! example: [ harper steven, hawking john, ingleton steven]

my believed answer:

i beleive o(n) because it's going on elements of array comparing array[0] array[1] , array[2] array[3] ect ect. process linear , continues until last 2 compared. not logn because aren't multiplying or diving 2.

final question: suppose have box of folders each containing info on 1 person. if want people same first name, first start placing sticker on first folder in box , going through folders after in orderly fashion until find person same name. if find folder same name, move folder next folder sticker. once find 1 case 2 people have same name, stop , go sleep because we're lazy. if first search fails however, remove sticker , place on next folder , continue did earlier. repeat process until sticker on last folder in scenario have no 2 people same name.

this array not sorted , compares first folder sticker folder[0] next folder[i] elements.

my answer:

i feel can't o(n), maybe o(n^2) kinda feels have array , keep repeating process n proportional square of input(folders). wrong here through >.>

you're right on both questions… but explain things bit more rigorously. don't know standards of class are; don't need actual proof, showing more detailed reasoning "we aren't multiplying or dividing two" never hurts. so…

---

in first question, there's nothing happening here comparisons, that's have count.

and worst case have go through whole array.

so, in case, have compare a[0] == a[1], a[1] == a[2], …, a[n-1] == a[n]. each of n-1 elements, there's 1 comparison. that's n-1 steps, o(n).

the fact array sorted turns out irrelevant here. (of course since they're not sorted search key—that is, they're sorted last name, you're comparing first name—that pretty obvious.)

---

in second question, there 2 things happening here: comparisons, , moves.

for comparisons, worst case have n searches because there no matches. say, start a[0] vs. a[1], …, a[n]; a[1] vs. a[2], …, a[n], etc. so, n-1 comparisons, n-2, , on down 0. total number of comparisons sum(0…n-1), n*(n-1)/2, or n^2/2 - n/2, o(n^2).

for moves, worst case find match between a[0] , a[n]. in case, have swap a[n] a[n-1], a[n-1] a[n-2], , on until you've swapped a[2] a[1]. so, that's n-1 swaps, o(n), can ignore because you've got o(n^2) term.

---

as side note, i'm not sure description whether you're talking array a[0…n], or array of length n, a[0…n-1], there off-by-one error in both of above. should pretty easy prove doesn't make difference.