공주 구하기 문제 풀이 시간 복잡도 질문

안녕하세요

제가 푼 코드와 강의의 풀이가 차이가 있어서 질문 드립니다.

저는 아래와 같이 문제를 풀어 봤는데요.

강의와 제 풀이의 시간 복잡도가 어떻게 되는건지 궁금합니다.

제 풀이는 while문이 하나 있으니 O(n)으로 표시하면 되는 것일까요?

강의 풀이는 while문 안에 for문이 있는데 그럼 O(n^2) 인건가요? 아니면 K를 상수로 보고 O(n) 이라고 생각하면 되는 걸까요..

    public int solution(int n, int k) {
        int answer = 0;
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }

        int cnt = 1;
        while (queue.size() > 0) {
            if (cnt == k) {
                answer = queue.poll();
                cnt = 1;
            } else {
                queue.add(queue.poll());
                cnt++;
            }
        }

        return answer;
    }

두 코드 중 어떤 것이 더 효율적인 코드인지 궁금합니다.

실행 시간을 비교해서 더 짧게 나오는 것이 효율적인 코드라고 봐도 되는 걸까요?