I'm trying to write a small algorithm to detect and delete duplicate lines inside a subset of consecutive lines in a file.I've come up with 2 similar solutions.After some quick tests, I've noticed that one of them is much faster than the other, especially on large files.But I don't understand why.Here's the quick solution written in pseudocode, first_line and last_line are the first and last lines in the file where the algorithm looks for duplicate lines (I don't know exactly how to write pseudocode sorry):i = last_linewhile i > first_line    j = i-1    while j >= first_line        if line i = line j            delete line i            break        endif        j = j-1    endwhile    i = i-1endwhileAnd here's the slow solution:i = last_linewhile i > first_line    j = i-1    while j >= first_line        if line i = line j            delete line j        endif        j = j-1    endwhile    i = i-1endwhileIn the first solution, when 2 duplicate lines are detected and whose addresses are i and j,line i is deleted, and the inner loop exits.In the 2nd solution, line j is deleted, and the inner loop goes on without being broken.At first, intuitively, I thought that choosing to delete i or j didn't matter.But after some tests, it seems deleting i results in a much quicker process than deleting j.I don't understand the asymmetry.I suspect it's because the purpose of the outer loop is to test the uniqueness of the line whose addressis i, so it would make more sense to delete it as soon as we have an answer and not let the loop goes on.But I still don't understand completely.Deleting line i and exiting earlier in the inner loop of the first solution save comparison operations.But by deleting line j in the 2nd solution, I also save comparison operations, since this j line won'tbe processed by the outer loop later.Why is the first saving of operations much more important than the 2nd one?I'm sorry if the question is too simple for this site, but I don't know much about algorithms,and I'm looking for a reasoning which I can understand and would prove that in the general case, deleting ireduce the number of operations.In case it matters, here's the real code I'm using, it's written in vimscript:com! -range=% DelDup call s:del_dup(<line1>,<line2>)fu! s:del_dup(line1, line2) abort    let view = winsaveview()    let p    = a:line2    while p > a:line1        let q = a:line1        while q < p            if getline(p) ==# getline(q)                exe p . 'd_' | break            endif            let q += 1        endwhile        let p -= 1    endwhile    call winrestview(view)endfuEdit:I've compared the 2 algorithms with this simple file:applebananagrapekiwiorangetangerineThen, duplicate each line 256 times:for i in range(1, 8) | sil %t$ | endforWhich gives a file with 1536 lines.Then, I've measured the time it takes for the :DelDup command to delete duplicate lines with the fast algorithm which I wrote earlier::Time DelDupOn my machine, the time reported is around 0.1s.But if I replace the lines:if getline(p) ==# getline(q)    exe p . 'd_' | breakendifWith these lines:if getline(p) ==# getline(q)    exe q . 'd_'endifThen :Time DelDup reports that the command took more than 8s on average.In case it matters, here's how the :Time command is defined:com! -count=1 -nargs=+ -complete=command Time call s:time(<q-args>, <count>)fu! s:time(cmd, cnt)    let time = reltime()    try        if a:cnt > 1        let i = 0        while i < a:cnt            exe a:cmd            let i += 1        endwhile        else            exe a:cmd        endif    finally        redraw        echomsg matchstr(reltimestr(reltime(time)), '\v.*\..{,3}') . ' seconds to run :' . a:cmd    endtryendfu
Why don't these 2 algorithms take the same time to detect duplicate lines in a file?
time complexity
When you delete line j, each line which was after that line will be moved by one line upwards. That means, that your line i, which is below, also will be moved. So, since it was moved, it has changed it's number. And it means that you need to decrease i : i = i - 1.As an example see this:Given file:    Lines 2 and 3 are equal    Remove line 2:1 00                                      1 002 01                                      3 10                                      2 104 01                                      3 01And your second algorithm didn't see that their positions have changed. However, if it wouldn't be file, but an array/list/etc, you'd got an error.